{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:05Z","timestamp":1777516745984,"version":"3.51.4"},"reference-count":30,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2017,3,1]],"date-time":"2017-03-01T00:00:00Z","timestamp":1488326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2017,3,16]]},"abstract":"<jats:p>An \u03b1-automaton (for \u03b1 some ordinal) is an automaton similar to a Muller automaton that processes words of length \u03b1. A structure is called \u03b1-automatic if it can be presented by \u03b1-automata (completely analogous to the notion of automatic structures which can be presented by the well-known finite automata). We call a structure ordinal-automatic if it is \u03b1-automatic for some ordinal \u03b1. We continue the study of ordinal-automatic structures initiated by Schlicht and Stephan as well as by Finkel and Todor\u010devi\u0107. We develop a pumping lemma for \u03b1-automata (processing finite \u03b1-words, i.e., words of length \u03b1 that have one fixed letter at all but finitely many positions). Using this pumping, we provide counterparts for the class of ordinal-automatic structures to several results on automatic structures:<\/jats:p>\n                  <jats:p>\u2219 Every finite word \u03b1-automatic structure has an injective finite word \u03b1-automatic presentation for all [Formula: see text]. This bound is sharp.<\/jats:p>\n                  <jats:p>\u2219 We classify completely the finite word [Formula: see text]-automatic Boolean algebras. Moreover, we show that the countable atomless Boolean algebra does not have an injective finite-word ordinal-automatic presentation.<\/jats:p>\n                  <jats:p>\u2219 We separate the class of finite-word ordinal-automatic structures from that of tree-automatic structures by showing that free term algebras with at least 2 generators (and one binary function) are not ordinal-automatic while the free term algebra with countable infinitely many generators is known to be tree-automatic.<\/jats:p>\n                  <jats:p>\u2219 For every ordinal [Formula: see text], we provide a sharp bound on the height of the finite word \u03b1-automatic well-founded order forests.<\/jats:p>\n                  <jats:p>\u2219 For every ordinal [Formula: see text], we provide a structure [Formula: see text] that is complete for the class of finite-word \u03b1-automatic structures with respect to first-order interpretations.<\/jats:p>\n                  <jats:p>\u2219 As a byproduct, we also lift Schlicht and Stephans\u2019s characterisation of the injectively finite-word \u03b1-automatic ordinals to the noninjective setting.<\/jats:p>","DOI":"10.3233\/com-160057","type":"journal-article","created":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T10:39:38Z","timestamp":1489142378000},"page":"125-164","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Pumping for ordinal-automatic structures"],"prefix":"10.1177","volume":"6","author":[{"given":"Martin","family":"Huschenbett","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Ludwig-Maximilians-Universit\u00e4t M\u00fcnchen, M\u00fcnchen, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Kartzow","sequence":"additional","affiliation":[{"name":"Department f\u00fcr Elektrotechnik und Informatik, Universit\u00e4t Siegen, Siegen, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Schlicht","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Mathematische Logik und Grundlagenforschung, Universit\u00e4t M\u00fcnster, M\u00fcnster, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2017,3,1]]},"reference":[{"key":"ref001","doi-asserted-by":"crossref","unstructured":"F.\u00a0Baader and T.\u00a0Nipkow, Term Rewriting and All That, Cambridge University Press, 1998.","DOI":"10.1017\/CBO9781139172752"},{"key":"ref002","unstructured":"A.\u00a0Blumensath, Automatic structures, Diploma thesis, RWTH Aachen, 1999."},{"key":"ref003","doi-asserted-by":"crossref","unstructured":"A.\u00a0Blumensath and E.\u00a0Gr\u00e4del, Automatic structures, in: Proc. 15th IEEE Symp. on Logic in Computer Science, 2000, pp.\u00a051\u201362.","DOI":"10.1109\/LICS.2000.855755"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1965-11384-2"},{"key":"ref005","doi-asserted-by":"crossref","unstructured":"J.R.\u00a0B\u00fcchi, The monadic second order theory of\n                      \u03c9\n                      1\n                      , in: Decidable Theories II, G.H.\u00a0M\u00fcller and D.\u00a0Siefkes, eds, Lecture Notes in Mathematics, Vol.\u00a0328, Springer, Berlin, Heidelberg, 1973, pp.\u00a01\u2013127.","DOI":"10.1007\/BFb0082721"},{"key":"ref006","doi-asserted-by":"crossref","unstructured":"O.\u00a0Carton, Accessibility in automata on scattered linear orderings, in: MFCS, K.Diks and W.Rytter, eds, Lecture Notes in Computer Science, Vol.\u00a02420, Springer, 2002, pp.\u00a0155\u2013164.","DOI":"10.1007\/3-540-45687-2_12"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2004.03.035"},{"key":"ref008","unstructured":"O.\u00a0Finkel and S.\u00a0Todor\u010devi\u0107, A hierarchy of tree-automatic structures,\n                      CoRR\n                      , 2011, http:\/\/arxiv.org\/abs\/1111.1504."},{"key":"ref009","unstructured":"O.\u00a0Finkel and S.\u00a0Todor\u010devi\u0107, Automatic ordinals,\n                      CoRR\n                      , 2012, http:\/\/arxiv.org\/abs\/1205.1775."},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1327068708"},{"issue":"1","key":"ref011","first-page":"61","volume":"9","author":"Finkel O.","year":"2013","journal-title":"IJUC"},{"key":"ref012","unstructured":"S.S.\u00a0Goncharov, Countable Boolean Algebras and Decidability, Siberian School of Algebra and Logic, Springer, 1997."},{"key":"ref013","unstructured":"W.\u00a0Hodges, A Shorter Model Theory, Cambridge University Press, 1997."},{"key":"ref014","unstructured":"M.\u00a0Huschenbett, The rank of tree-automatic linear orderings, in: STACS, N.\u00a0Portier and T.\u00a0Wilke, eds, LIPIcs, Vol.\u00a020, Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 2013, pp.\u00a0586\u2013597."},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"A.\u00a0Kartzow, J.\u00a0Liu and M.\u00a0Lohrey, Tree-automatic well-founded trees, in: Proc. CIE 2012, Lecture Notes in Computer Science, Springer-Verlag, 2012.","DOI":"10.1007\/978-3-642-30870-3_37"},{"key":"ref016","doi-asserted-by":"crossref","unstructured":"A.\u00a0Kartzow, J.\u00a0Liu and M.\u00a0Lohrey, Tree-automatic well-founded trees, in: How the World Computes \u2013 Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18\u201323, 2012. Proceedings, S.B.\u00a0Cooper, A.\u00a0Dawar and B.\u00a0L\u00f6we, eds, Lecture Notes in Computer Science, Vol.\u00a07318, Springer, pp.\u00a0363\u2013373.","DOI":"10.1007\/978-3-642-30870-3_37"},{"key":"ref017","doi-asserted-by":"crossref","unstructured":"A.\u00a0Kartzow, J.\u00a0Liu and M.\u00a0Lohrey, Tree-automatic well-founded trees,\n                      CoRR\n                      , http:\/\/arxiv.org\/abs\/1201.5495, 2012, Version 1.","DOI":"10.1007\/978-3-642-30870-3_37"},{"key":"ref018","unstructured":"A.\u00a0Kartzow and P.\u00a0Schlicht, Structures without scattered-automatic presentation, in: The Nature of Computation. Logic, Algorithms, Applications \u2013 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1\u20135, 2013. Proceedings, P.\u00a0Bonizzoni, V.\u00a0Brattka and B.\u00a0L\u00f6we, eds, Lecture Notes in Computer Science, Vol.\u00a07921, Springer, 2013, pp.\u00a0273\u2013283."},{"key":"ref019","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.07.012"},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"B.\u00a0Khoussainov and A.\u00a0Nerode, Automatic presentations of structures, in: LCC, 1994, pp.\u00a0367\u2013392.","DOI":"10.1007\/3-540-60178-3_93"},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"B.\u00a0Khoussainov and A.\u00a0Nerode, Automata Theory and Its Applications, Progress in Computer Science and Applied Logic, Vol.\u00a021, Birkh\u00e4user, 2001.","DOI":"10.1007\/978-1-4612-0171-7"},{"issue":"2","key":"ref022","first-page":"1","volume":"3","author":"Khoussainov B.","year":"2007","journal-title":"Logical Methods in Computer Science"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1145\/1094622.1094625"},{"key":"ref024","unstructured":"S.\u00a0Koppelberg, Handbook of Boolean Algebras, Vol.\u00a01, North Holland, 1989."},{"key":"ref025","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2013-05766-2"},{"key":"ref026","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1208359052"},{"key":"ref027","unstructured":"I.\u00a0Neeman, Monadic definability of welders, in: Logic, Methodology and Philosophy of Science. Proceedings of the Thirteenth International Congress, W.G.\u00a0Wei, ed. College Publications, 2009, pp.\u00a0108\u2013121."},{"key":"ref028","unstructured":"J.G.\u00a0Rosenstein, Linear Orderings, Academic Press, 1982."},{"key":"ref029","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2012.11.007"},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.3233\/FI-1984-7203"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-160057","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-160057","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-160057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:59:52Z","timestamp":1777391992000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-160057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,1]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,3,16]]}},"alternative-id":["10.3233\/COM-160057"],"URL":"https:\/\/doi.org\/10.3233\/com-160057","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,1]]}}}