{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T05:34:53Z","timestamp":1790832893401,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T00:00:00Z","timestamp":1594166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,8]]},"DOI":"10.1145\/3373718.3394734","type":"proceedings-article","created":{"date-parts":[[2020,5,26]],"date-time":"2020-05-26T00:23:18Z","timestamp":1590452598000},"page":"21-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Automatic Structures"],"prefix":"10.1145","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[{"name":"Mathematical Foundations of Computer Science, RWTH Aachen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Faried Abu Zaid. 2016. Algorithmic Solutions via Model Theoretic Interpretations. Ph.D. Dissertation. RWTH Aachen University.  Faried Abu Zaid. 2016. Algorithmic Solutions via Model Theoretic Interpretations. Ph.D. Dissertation. RWTH Aachen University."},{"key":"e_1_3_2_1_2_1","unstructured":"Faried Abu Zaid Erich Gr\u00e4del \u0141ukasz Kaiser and Wied Pakusa. 2013. Model-Theoretic Properties of omega-Automatic Structures. Theory of Computing Systems Special Issue dedicated to STACS 2012 (2013).  Faried Abu Zaid Erich Gr\u00e4del \u0141ukasz Kaiser and Wied Pakusa. 2013. Model-Theoretic Properties of omega-Automatic Structures. Theory of Computing Systems Special Issue dedicated to STACS 2012 (2013)."},{"key":"e_1_3_2_1_3_1","volume-title":"Advice Automatic Structures and Uniformly Automatic Classes. In 26th EACSL Annual Conference on Computer Science Logic (CSL","author":"Zaid Faried Abu","year":"2017"},{"key":"e_1_3_2_1_4_1","volume-title":"27th EACSL Annual Conference on Computer Science Logic, CSL 2018 (LIPIcs)","volume":"119","author":"Zaid Faried Abu","year":"2018"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the International Symposium on Theoretical Aspects of Computer Science, STACS 2006 (LNCS), B. Durand and W. Thomas (Eds.)","volume":"3884","author":"B\u00e1r\u00e1ny Vince","year":"2006"},{"key":"e_1_3_2_1_6_1","unstructured":"Vince B\u00e1r\u00e1ny. 2007. Automatic Presentations of Infinite Structures. Dissertation. RWTH Aachen University.  Vince B\u00e1r\u00e1ny. 2007. Automatic Presentations of Infinite Structures. Dissertation. RWTH Aachen University."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Vince B\u00e1r\u00e1ny Erich Gr\u00e4del and Sasha Rubin. 2011. Automata-Based Presentations of Infinite Structures. In Finite and Algorithmic Model Theory Javier Esparza Christian Michaux and Charles Steinhorn (Eds.). 1--76.  Vince B\u00e1r\u00e1ny Erich Gr\u00e4del and Sasha Rubin. 2011. Automata-Based Presentations of Infinite Structures. In Finite and Algorithmic Model Theory Javier Esparza Christian Michaux and Charles Steinhorn (Eds.). 1--76.","DOI":"10.1017\/CBO9780511974960.002"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2019.26"},{"key":"e_1_3_2_1_9_1","unstructured":"Achim Blumensath. 1999. Automatic Structures. Diploma thesis RWTH Aachen University.  Achim Blumensath. 1999. Automatic Structures. Diploma thesis RWTH Aachen University."},{"key":"e_1_3_2_1_10_1","volume-title":"Automatic Structures. In Proceedings of IEEE Symposium on Logic in Computer Science LICS","author":"Blumensath Achim","year":"2000"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1133-y"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.36045\/bbms\/1103408547"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the International Congress on Logic, Methodology and Philosophy of Science. 1--11","author":"B\u00fcchi J. Richard","year":"1962"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1146620059"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90008-A"},{"key":"e_1_3_2_1_17_1","unstructured":"Thomas Colcombet. 2004. Propri\u00e9t\u00e9s et repr\u00e9sentation de structures infinies. Th\u00e8se de Doctorat. Universit'e de Rennes I.  Thomas Colcombet. 2004. Propri\u00e9t\u00e9s et repr\u00e9sentation de structures infinies. Th\u00e8se de Doctorat. Universit'e de Rennes I."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Thomas Colcombet and Christof L\u00f6ding. 2007. Transforming structures by set interpretations. Logical Methods in Computer Science 3 2 (2007).  Thomas Colcombet and Christof L\u00f6ding. 2007. Transforming structures by set interpretations. Logical Methods in Computer Science 3 2 (2007).","DOI":"10.2168\/LMCS-3(2:4)2007"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2004.03.035"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/2269808"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"David Epstein James Cannon Derek Holt Silvio Levy Mike Paterson and William Thurston. 1992. Word Processing in Groups. Jones and Bartlett Publishers Boston.  David Epstein James Cannon Derek Holt Silvio Levy Mike Paterson and William Thurston. 1992. Word Processing in Groups. Jones and Bartlett Publishers Boston.","DOI":"10.1201\/9781439865699"},{"key":"e_1_3_2_1_22_1","first-page":"291","article-title":"Automatic Groups","volume":"38","author":"Farb Benson","year":"1992","journal-title":"A Guided Tour. L'Enseignement Math\u00e9matique"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2478\/s11533-010-0014-7"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90051-X"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.28"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Wilfrid Hodges. 1993. Model Theory. Cambridge University Press.  Wilfrid Hodges. 1993. Model Theory. Cambridge University Press.","DOI":"10.1017\/CBO9780511551574"},{"key":"e_1_3_2_1_27_1","unstructured":"Bernard R. Hodgson. 1976. Th\u00e9ories d\u00e9cidables par automate fini. Ph.D. Thesis. Universit\u00e9 de Montr\u00e9al.  Bernard R. Hodgson. 1976. Th\u00e9ories d\u00e9cidables par automate fini. Ph.D. Thesis. Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90042-1"},{"key":"e_1_3_2_1_29_1","first-page":"39","article-title":"D\u00e9cidabilit\u00e9 par automate fini. Ann. sc. math","volume":"7","author":"Hodgson Bernard R.","year":"1983","journal-title":"Qu\u00e9bec"},{"key":"e_1_3_2_1_30_1","unstructured":"Martin Huschenbett. 2016. The model-theoretic complexity of automatic linear orders. Ph.D. Dissertation. Technische Universit\u00e4t Ilmenau Germany.  Martin Huschenbett. 2016. The model-theoretic complexity of automatic linear orders. Ph.D. Dissertation. Technische Universit\u00e4t Ilmenau Germany."},{"key":"e_1_3_2_1_31_1","volume-title":"Lecture Notes in Computer Science","volume":"6810","author":"Kaiser \u0141ukasz","year":"2011"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the International Symposium on Theoretical Aspects of Computer Science, STACS","author":"Kaiser \u0141ukasz","year":"2008"},{"key":"e_1_3_2_1_33_1","unstructured":"Alexander Kartzow. 2011. First-Order Model Checking on Generalisations of Pushdown Graphs. Ph.D. Thesis. TU Darmstadt.  Alexander Kartzow. 2011. First-Order Model Checking on Generalisations of Pushdown Graphs. Ph.D. Thesis. TU Darmstadt."},{"key":"e_1_3_2_1_34_1","series-title":"Lecture Notes in Computer Science","volume-title":"The Nature of Computation. Logic, Algorithms, Applications","author":"Kartzow Alexander"},{"key":"e_1_3_2_1_35_1","unstructured":"Olga Kharlampovich Bakhadyr Khoussainov and Alexei Miasnikov. 2011. From automatic structures to automatic groups. CoRR abs\/1107.3645 (2011).  Olga Kharlampovich Bakhadyr Khoussainov and Alexei Miasnikov. 2011. From automatic structures to automatic groups. CoRR abs\/1107.3645 (2011)."},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of Logic Colloquium. 132\u00e2\u0102\u0164-176","author":"Khoussainov Bakhadyr","year":"2007"},{"key":"e_1_3_2_1_37_1","volume-title":"Logic and Computational Complexity. Number 960 in Lecture Notes in Computer Science","author":"Khoussainov Bakhadyr"},{"key":"e_1_3_2_1_38_1","volume-title":"Automatic Structures: Richness and Limitations. Logical Methods in Computer Science 3, 2","author":"Khoussainov Bakhadyr","year":"2007"},{"key":"e_1_3_2_1_39_1","volume-title":"Definability and Regularity in Automatic Structures. In STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science (Lecture Notes in Computer Science)","volume":"2996","author":"Khoussainov Bakhadyr","year":"2004"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1094622.1094625"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.96.18"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03564-7_5"},{"key":"e_1_3_2_1_43_1","volume-title":"Proceedings of the International Symposium on Theoretical Aspects of Computer Science, STACS","author":"Kuske Dietrich","year":"2010"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.10"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2012.09.001"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1208358745"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09680-3_30"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1318338854"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39813-4_25"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1186666149"},{"key":"e_1_3_2_1_51_1","unstructured":"Dominique Perrin and Jean-Eric Pin. 2004. Infinite words - automata semigroups logic and games. Pure and applied mathematics series Vol. 141. Elsevier Morgan Kaufmann.  Dominique Perrin and Jean-Eric Pin. 2004. Infinite words - automata semigroups logic and games. Pure and applied mathematics series Vol. 141. Elsevier Morgan Kaufmann."},{"key":"e_1_3_2_1_52_1","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"41","author":"Rabin Michael O.","year":"1969","journal-title":"Transactions of the AMS"},{"key":"e_1_3_2_1_53_1","unstructured":"Sascha Rubin. 2004. Automatic Structures. PhD Thesis. University of Auckland.  Sascha Rubin. 2004. Automatic Structures. PhD Thesis. University of Auckland."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1208442827"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-41-2-203-271"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Alfred Tarski. 1951. A Decision Method for Elementary Algebra and Geometry. University of California Press.  Alfred Tarski. 1951. A Decision Method for Elementary Algebra and Geometry. University of California Press.","DOI":"10.1525\/9780520348097"},{"key":"e_1_3_2_1_57_1","volume-title":"Handbook of Theoretical Computer Science","author":"Thomas W."},{"key":"e_1_3_2_1_58_1","volume-title":"Handbook of formal languages","author":"Thomas Wolfgang"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1318338853"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196793000287"}],"event":{"name":"LICS '20: 35th Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Saarbr\u00fccken Germany","acronym":"LICS '20","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"]},"container-title":["Proceedings of the 35th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394734","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373718.3394734","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:35Z","timestamp":1750197755000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373718.3394734"}},"subtitle":["Twenty Years Later"],"short-title":[],"issued":{"date-parts":[[2020,7,8]]},"references-count":60,"alternative-id":["10.1145\/3373718.3394734","10.1145\/3373718"],"URL":"https:\/\/doi.org\/10.1145\/3373718.3394734","relation":{},"subject":[],"published":{"date-parts":[[2020,7,8]]},"assertion":[{"value":"2020-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}