{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T08:05:46Z","timestamp":1772438746169,"version":"3.50.1"},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":1380,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For automatic and recursive graphs, we investigate the following problems:<\/jats:p><jats:p>(A) existence of a Hamiltonian path and existence of an infinite path in a tree<\/jats:p><jats:p>(B) existence of an Euler path, bounding the number of ends, and bounding the number of infinite branches in a tree<\/jats:p><jats:p>(C) existence of an infinite clique and an infinite version of set cover<\/jats:p><jats:p>The complexity of these problems is determined for automatic graphs and. supplementing results from the literature, for recursive graphs. Our results show that these problems<\/jats:p><jats:p>(A) are equally complex for automatic and for recursive graphs (<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200002723_inline1\"\/>-complete).<\/jats:p><jats:p>(B) are moderately less complex for automatic than for recursive graphs (complete for different levels of the arithmetic hierarchy),<\/jats:p><jats:p>(C) are much simpler for automatic than for recursive graphs (decidable and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200002723_inline1\"\/>-complete, resp.).<\/jats:p>","DOI":"10.2178\/jsl\/1268917499","type":"journal-article","created":{"date-parts":[[2010,3,18]],"date-time":"2010-03-18T09:05:57Z","timestamp":1268903157000},"page":"678-710","source":"Crossref","is-referenced-by-count":13,"title":["Some natural decision problems in automatic graphs"],"prefix":"10.1017","volume":"75","author":[{"given":"Dietrich","family":"Kuske","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200002723_ref037","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1961.tb03975.x"},{"key":"S0022481200002723_ref036","first-page":"130","volume-title":"DLT 2001","author":"Thomas","year":"2001"},{"key":"S0022481200002723_ref035","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1208442827"},{"key":"S0022481200002723_ref034","unstructured":"Rubin S. , Automatic structures, Ph.D. thesis, University of Auckland, 2004."},{"key":"S0022481200002723_ref033","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1968"},{"key":"S0022481200002723_ref030","first-page":"445","volume-title":"IFIP-TCS 2008","author":"Kuske","year":"2008"},{"key":"S0022481200002723_ref029","first-page":"129","volume":"73","author":"Kuske","year":"2008","journal-title":"First-order and counting theories of co-automatic structures"},{"key":"S0022481200002723_ref026","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1943-0007371-8"},{"key":"S0022481200002723_ref025","doi-asserted-by":"publisher","DOI":"10.1145\/1094622.1094625"},{"key":"S0022481200002723_ref023","first-page":"168","volume-title":"LICS 2003","author":"Khoussainov","year":"2003"},{"key":"S0022481200002723_ref022","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(2:2)2007"},{"key":"S0022481200002723_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60178-3_93"},{"key":"S0022481200002723_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773868"},{"key":"S0022481200002723_ref017","doi-asserted-by":"publisher","DOI":"10.1145\/4904.4993"},{"key":"S0022481200002723_ref016","first-page":"51","article-title":"Recurring dominoes: making the highly undecidable highly understandable","volume":"24","author":"Harel","year":"1985","journal-title":"Annals of Discrete Mathematics"},{"key":"S0022481200002723_ref012","first-page":"128","article-title":"Solutii problematis ad geometriam situs pertinentis","volume":"8","author":"Euler","year":"1736","journal-title":"Commentarii Academiae Scientiarum Petropolitanae"},{"key":"S0022481200002723_ref009","volume-title":"Groups acting on graphs","author":"Dicks","year":"1989"},{"key":"S0022481200002723_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1133-y"},{"key":"S0022481200002723_ref006","volume-title":"Automatic structures","author":"Blumensath","year":"1999"},{"key":"S0022481200002723_ref005","first-page":"72","article-title":"The undecidability of the domino problem","author":"Berger","year":"1966","journal-title":"Memoirs of the American Mathematical Society"},{"key":"S0022481200002723_ref004","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"S0022481200002723_ref003","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1976-0416888-0"},{"key":"S0022481200002723_ref002","first-page":"469","volume":"41","author":"Bean","year":"1976","journal-title":"Effective coloration"},{"key":"S0022481200002723_ref015","volume-title":"Proceedings of the Logic and Computation Conference","author":"Harel","year":"1984"},{"key":"S0022481200002723_ref027","volume-title":"Theory of Computation","author":"Kozen","year":"2006"},{"key":"S0022481200002723_ref011","doi-asserted-by":"publisher","DOI":"10.1002\/sapm193817159"},{"key":"S0022481200002723_ref020","first-page":"514","volume-title":"TAMC 2008","author":"Khoussainov","year":"2008"},{"key":"S0022481200002723_ref010","volume-title":"Graph theory","author":"Diestel","year":"2006"},{"key":"S0022481200002723_ref007","first-page":"51","volume-title":"LICS 2000","author":"Blumensath","year":"2000"},{"key":"S0022481200002723_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24749-4_39"},{"key":"S0022481200002723_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00065-5"},{"key":"S0022481200002723_ref028","first-page":"245","volume-title":"AFL 2008","author":"Kuske","year":"2008"},{"key":"S0022481200002723_ref013","doi-asserted-by":"publisher","DOI":"10.1137\/0205049"},{"key":"S0022481200002723_ref001","first-page":"385","volume-title":"STACS2008","author":"B\u00e1r\u00e1ny","year":"2008"},{"key":"S0022481200002723_ref014","first-page":"1041","volume-title":"Handbook of recursive mathematics","volume":"2","author":"Gasarch","year":"1998"},{"key":"S0022481200002723_ref032","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-25.4.615"},{"key":"S0022481200002723_ref019","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0060"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200002723","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T15:38:16Z","timestamp":1556465896000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200002723\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["S0022481200002723"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1268917499","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6]]}}}