{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T08:05:45Z","timestamp":1772438745148,"version":"3.50.1"},"reference-count":57,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":2054,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A structure has a (finite-string)<jats:italic>automatic presentation<\/jats:italic>if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a decidable first-order theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.<\/jats:p>","DOI":"10.2178\/bsl\/1208442827","type":"journal-article","created":{"date-parts":[[2008,4,17]],"date-time":"2008-04-17T18:38:08Z","timestamp":1208457488000},"page":"169-209","source":"Crossref","is-referenced-by-count":58,"title":["Automata Presenting Structures: A Survey of the Finite String Case"],"prefix":"10.1017","volume":"14","author":[{"given":"Sasha","family":"Rubin","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600001682_ref051","unstructured":"Rubin S. , Automatic structures, Ph.D. thesis, University of Auckland, 2004."},{"key":"S1079898600001682_ref023","unstructured":"Delhomm\u00e9 C. The Rado graph is not automatic, 2001, manuscript."},{"key":"S1079898600001682_ref048","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-31856-9_57","volume-title":"STACS 2005","volume":"3404","author":"Oliver","year":"2005"},{"key":"S1079898600001682_ref047","volume-title":"FA-presentable groups and rings","author":"Nies","year":"2005"},{"key":"S1079898600001682_ref004","volume-title":"STACS 2008","volume":"08001","author":"B\u00e1r\u00e1ny","year":"2008"},{"key":"S1079898600001682_ref040","first-page":"178","volume-title":"LICS 2003","author":"Libkin","year":"2003"},{"key":"S1079898600001682_ref044","first-page":"939","article-title":"Les ensembles k-reconnaissables sont d\u00e9finissables dans \u3008N, +, Vk\u3009","volume":"303","author":"Michaux","year":"1986","journal-title":"Comptes Rendus des S\u00e9ances de l'Acad\u00e9mie des Sciences. S\u00e9rie I. Math\u00e9matique"},{"key":"S1079898600001682_ref011","first-page":"596","volume-title":"STACS","volume":"2285","author":"Alt","year":"2002"},{"key":"S1079898600001682_ref032","first-page":"39","article-title":"Decidabilite par automate fini","volume":"7","author":"Hodgson","year":"1983","journal-title":"Annales de Sciences Math\u00e9matiques du Qu\u00e9bec"},{"key":"S1079898600001682_ref037","doi-asserted-by":"publisher","DOI":"10.1145\/1094622.1094625"},{"key":"S1079898600001682_ref003","unstructured":"B\u00e1r\u00e1ny V. Automatic presentations of infinite structures, Ph.D. thesis, RWTH Aachen, 2007."},{"key":"S1079898600001682_ref049","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"S1079898600001682_ref016","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S1079898600001682_ref043","first-page":"344","volume-title":"LPAR 2003","volume":"2850","author":"Lohrey","year":"2003"},{"key":"S1079898600001682_ref009","unstructured":"Blumensath A. , Automatic structures, Diploma thesis, Rwth Aachen, 1999."},{"key":"S1079898600001682_ref028","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021758312697"},{"key":"S1079898600001682_ref007","doi-asserted-by":"publisher","DOI":"10.1147\/rd.176.0525"},{"key":"S1079898600001682_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(98)80011-6"},{"key":"S1079898600001682_ref027","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"S1079898600001682_ref055","first-page":"133","volume-title":"Handbook of theoretical computer science","volume":"B","author":"Thomas","year":"1990"},{"key":"S1079898600001682_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_23"},{"key":"S1079898600001682_ref050","volume-title":"Linear orderings","author":"Rosenstein","year":"1982"},{"key":"S1079898600001682_ref054","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"},{"key":"S1079898600001682_ref025","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80041-1"},{"key":"S1079898600001682_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2004.03.035"},{"key":"S1079898600001682_ref005","first-page":"203","volume-title":"LICS 2002","author":"Benedikt","year":"2002"},{"key":"S1079898600001682_ref038","first-page":"332","volume-title":"LPAR","volume":"2850","author":"Kuske","year":"2003"},{"key":"S1079898600001682_ref015","doi-asserted-by":"crossref","first-page":"191","DOI":"10.36045\/bbms\/1103408547","article-title":"Logic and p-recognizable sets of integers","volume":"1","author":"Bruy\u00e8re","year":"1994","journal-title":"Bulletin of the Belgian Mathematical Society. Simon Stevin"},{"key":"S1079898600001682_ref012","first-page":"51","volume-title":"LICS 2000","author":"Blumensath","year":"2000"},{"key":"S1079898600001682_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90042-1"},{"key":"S1079898600001682_ref001","first-page":"26","volume-title":"Aspects of effective algebra (clayton, 1979)","author":"Ash","year":"1981"},{"key":"S1079898600001682_ref030","unstructured":"Hodgson B. R. , Th\u00e9ories d\u00e9cidables par automate fini, Ph.D. thesis, University of Montr\u00e9al, 1976."},{"key":"S1079898600001682_ref006","first-page":"431","volume-title":"LICS 2001","author":"Benedikt","year":"2001"},{"key":"S1079898600001682_ref014","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1133-y"},{"key":"S1079898600001682_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"S1079898600001682_ref035","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(2:2)2007"},{"key":"S1079898600001682_ref052","volume-title":"The random graph is not automatically presentable","author":"Stephan","year":"2002"},{"key":"S1079898600001682_ref013","volume-title":"Proceedings of the 2nd International Workshop on Complexity in Automated Deduction, CiAD 2002","author":"Blumensath","year":"2002"},{"key":"S1079898600001682_ref026","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(69)90107-0"},{"key":"S1079898600001682_ref053","first-page":"494","volume-title":"MFCS '92","volume":"629","author":"Szilard","year":"1992"},{"key":"S1079898600001682_ref056","first-page":"103","article-title":"Finite automata and the logic of one-place predicates","volume":"3","author":"Trahtenbrot","year":"1962","journal-title":"Siberian Mathematical Journal"},{"key":"S1079898600001682_ref046","unstructured":"Nies A. , Describing Groups, this Bulletin, vol. 13 (2007), no. 3, pp. 305\u2013339."},{"key":"S1079898600001682_ref021","doi-asserted-by":"crossref","unstructured":"Colcombet T. and C. L\u00f6ding , Transforming structures by set interpretations, Technical Report AIB-2006-07, RWTH Aachen, 2006.","DOI":"10.2168\/LMCS-3(2:4)2007"},{"key":"S1079898600001682_ref022","unstructured":"Delhomm\u00e9 C. , Non-automaticity of \u03c9\u03c9 , 2001, manuscript."},{"key":"S1079898600001682_ref039","unstructured":"Kuske D. and Lohrey M. , First-order and counting theories of omega-automatic structures, Fakultatsbericht Nr. 2005\/07, Universit\u00e4t Stuttgart, Fakult\u00e4t Informatik, Elektrotechnik und Informationstechnik, September 2005."},{"key":"S1079898600001682_ref017","first-page":"1","volume-title":"Logic, methodology and philosophy of science","author":"B\u00fcchi","year":"1962"},{"key":"S1079898600001682_ref036","first-page":"440","volume-title":"STACS","volume":"2996","author":"Khoussainov","year":"2004"},{"key":"S1079898600001682_ref019","volume-title":"Word processing in groups","author":"Cannon","year":"1992"},{"key":"S1079898600001682_ref042","unstructured":"L\u00f6ding Christof , Infinite graphs generated by tree rewriting, Ph.D. thesis, RWTH Aachen, 2003."},{"key":"S1079898600001682_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90070-5"},{"key":"S1079898600001682_ref033","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1090\/dimacs\/025\/05","volume-title":"Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994)","volume":"25","author":"Holt","year":"1996"},{"key":"S1079898600001682_ref034","volume":"960","author":"Khoussainov","year":"1995","journal-title":"Automatic presentations of structures"},{"key":"S1079898600001682_ref010","unstructured":"Prefix-recognisable graphs and monadic second-order logic, Technical report, RWTH Aachen, 2001."},{"key":"S1079898600001682_ref057","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90256-F"},{"key":"S1079898600001682_ref045","first-page":"7","article-title":"Multitape automata in a unary alphabet","volume":"292","author":"Nabebin","year":"1976","journal-title":"Trudy Moskovskogo Ordena Lenina \u00c8nergeticheskogo Instituta"},{"key":"S1079898600001682_ref018","first-page":"123","article-title":"The combinatorial structure of cocompact discrete hyperbolic groups","volume":"16","author":"Cannon","year":"1984","journal-title":"Geometriae Dedicata (Historical Archive)"},{"key":"S1079898600001682_ref041","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","article-title":"First order predicate logic with generalized quantifiers","volume":"32","author":"Lindstr\u00f6m","year":"1966","journal-title":"Theoria"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600001682","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,25]],"date-time":"2024-02-25T06:03:18Z","timestamp":1708840998000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600001682\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["S1079898600001682"],"URL":"https:\/\/doi.org\/10.2178\/bsl\/1208442827","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}