{"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":1772438746507,"version":"3.50.1"},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":832,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar results also for tree automatic structures. These findings close the gaps left open in [28] by improving both the lower and the upper bounds.<\/jats:p>","DOI":"10.2178\/jsl\/1318338854","type":"journal-article","created":{"date-parts":[[2011,10,11]],"date-time":"2011-10-11T10:32:16Z","timestamp":1318329136000},"page":"1352-1380","source":"Crossref","is-referenced-by-count":7,"title":["Automatic structures of bounded degree revisited"],"prefix":"10.1017","volume":"76","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":"S0022481200001420_ref034","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264285"},{"key":"S0022481200001420_ref032","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90281-J"},{"key":"S0022481200001420_ref031","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1208442827"},{"key":"S0022481200001420_ref030","volume-title":"Computational complexity","author":"Papadimitriou","year":"1994"},{"key":"S0022481200001420_ref027","first-page":"678","volume":"75","author":"Kuske","year":"2010","journal-title":"Some natural decision problems in automatic graphs"},{"key":"S0022481200001420_ref025","first-page":"81","volume-title":"Proceedings of CAI'09","volume":"5725","author":"Kuske"},{"key":"S0022481200001420_ref022","first-page":"168","volume-title":"Proceedings of LICS'03","author":"Khoussainov","year":"2003"},{"key":"S0022481200001420_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90042-1"},{"key":"S0022481200001420_ref015","doi-asserted-by":"crossref","DOI":"10.1201\/9781439865699","volume-title":"Word processing in groups","author":"Epstein","year":"1992"},{"key":"S0022481200001420_ref010","unstructured":"[] Comon H. , Dauchet M. , Gilleron R. , L\u00f6ding C. , Jacquemard F. , Lugiez D. , Tison S. , and Tommasi M. , Tree automata techniques and applications, available on http:\/\/www.grappa.univlille3.fr\/tata, release 10, 12th 2007, 2007."},{"key":"S0022481200001420_ref009","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(2:4)2007"},{"key":"S0022481200001420_ref008","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"S0022481200001420_ref007","first-page":"51","volume-title":"Proceedings of LICS'00","author":"Blumensath","year":"2000"},{"key":"S0022481200001420_ref004","first-page":"385","volume-title":"Proceedings of STACS'08","author":"B\u00e1r\u00e1ny","year":"2008"},{"key":"S0022481200001420_ref012","first-page":"913","volume-title":"Proceedings of ICALP 2007","volume":"4596","author":"Dawar","year":"2007"},{"key":"S0022481200001420_ref035","unstructured":"[] Weidner Th. , Die Gr\u00f6\u00dfe injektiver baumautomatischer Darstellungen und die Komplexit\u00e4t ihrer Berechnung, Diploma thesis, University of Leipzig, 2010, in German. English version in preparation."},{"key":"S0022481200001420_ref014","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"S0022481200001420_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60178-3_93"},{"key":"S0022481200001420_ref013","unstructured":"[] Delhomm\u00e9 Ch. , Goranko V. , and Knapik T. , Automatic linear orderings, manuscript, 2003."},{"key":"S0022481200001420_ref033","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/hah006"},{"key":"S0022481200001420_ref024","first-page":"332","volume-title":"Proceedings of LPAR'05","volume":"2850","author":"Kuske","year":"2003"},{"key":"S0022481200001420_ref006","unstructured":"[] Blumensath A. , Automatic structures, Diploma Thesis, RWTH Aachen, 1999."},{"key":"S0022481200001420_ref019","first-page":"235","volume-title":"Proceedings of LICS'02","author":"Ishihara","year":"2002"},{"key":"S0022481200001420_ref023","first-page":"440","volume-title":"Proceedings of STACS'04","volume":"2996","author":"Khoussainov","year":"2004"},{"key":"S0022481200001420_ref005","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876642"},{"key":"S0022481200001420_ref002","unstructured":"[] B\u00e1r\u00e1ny V. , Automatic presentations of infinite structure, Ph.D. thesis, RWTH Aachen, 2007."},{"key":"S0022481200001420_ref021","first-page":"467","article-title":"Graphs with automatic presentations over a unary alphabet","volume":"6","author":"Khoussainov","year":"2001","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0022481200001420_ref003","first-page":"1","volume-title":"Finite and algorithmic model theory","author":"B\u00e1r\u00e1ny","year":"2011"},{"key":"S0022481200001420_ref028","first-page":"344","volume-title":"Proceedings of LPAR'O3","volume":"2850","author":"Lohrey","year":"2003"},{"key":"S0022481200001420_ref026","first-page":"129","volume":"73","author":"Kuske","year":"2008","journal-title":"First-order and counting theories of \u03c9-automatic structures"},{"key":"S0022481200001420_ref001","first-page":"289","volume-title":"Proceedings of STACS'06","volume":"3884","author":"B\u00e1r\u00e1ny","year":"2006"},{"key":"S0022481200001420_ref029","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0064872"},{"key":"S0022481200001420_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90080-L"},{"key":"S0022481200001420_ref016","first-page":"105","volume-title":"Logic colloquium '81","author":"Gaifman","year":"1982"},{"key":"S0022481200001420_ref017","first-page":"431","volume-title":"Proceedings of LICS'08","author":"Hjorth","year":"2008"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200001420","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T21:54:55Z","timestamp":1556315695000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200001420\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["S0022481200001420"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1318338854","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}