{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T08:05:44Z","timestamp":1772438744299,"version":"3.50.1"},"reference-count":55,"publisher":"EDP Sciences","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1051\/ita:2008008","type":"journal-article","created":{"date-parts":[[2008,6,2]],"date-time":"2008-06-02T11:45:58Z","timestamp":1212407158000},"page":"417-450","source":"Crossref","is-referenced-by-count":2,"title":["A Hierarchy of Automatic<i>\u03c9<\/i>-Words having a Decidable MSO Theory"],"prefix":"10.1051","volume":"42","author":[{"given":"Vince","family":"B\u00e1r\u00e1ny","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2008,6,3]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"J.-P. Allouche and J. Shallit,Automatic Sequences, Theory, Applications, Generalizations. Cambridge University Press (2003).","DOI":"10.1017\/CBO9780511546563"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"J.-M. Autebert and J. Gabarr\u00f3, Iterated GSMs and Co-CFL.Acta Informatica26, 749\u2013769 (1989).","DOI":"10.1007\/BF00289160"},{"key":"R3","unstructured":"V. B\u00e1r\u00e1ny, Invariants of automatic presentations and semi-synchronous transductions. InSTACS '06. Lect. Notes Comput. Sci.3884, 289 (2006)."},{"key":"R4","unstructured":"V. B\u00e1r\u00e1ny,Automatic Presentations of Infinite Structures. Ph.D. thesis, RWTH Aachen (2007)."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"J. Berstel,Transductions and Context-Free Languages. Teubner, Stuttgart (1979).","DOI":"10.1007\/978-3-663-09367-1"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"D. Berwanger and A. Blumensath, The monadic theory of tree-like structures. InAutomata, Logics, and Infinite Games. Lect. Notes Comput. Sci.2500, 285\u2013301 (2002).","DOI":"10.1007\/3-540-36387-4_16"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"A. B\u00e8s, Undecidable extensions of B\u00fcchi arithmetic and Cobham-Sem\u00ebnov theorem.Journal of Symbolic Logic62, 1280\u20131296 (1997).","DOI":"10.2307\/2275643"},{"key":"R8","unstructured":"A. Blumensath, Automatic Structures. Diploma thesis, RWTH-Aachen (1999)."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"A. Blumensath, Axiomatising Tree-interpretable Structures. InSTACS. Lect. Notes Comput. Sci.2285, 596\u2013607 (2002).","DOI":"10.1007\/3-540-45841-7_49"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Blumensath and E. Gr\u00e4del, Finite presentations of infinite structures: Automata and interpretations.Theor. Comput. Syst.37, 641\u2013674 (2004).","DOI":"10.1007\/s00224-004-1133-y"},{"key":"R11","unstructured":"L. Braud, Higher-order schemes and morphic words. Journ\u00e9es Montoises, Rennes (2006)."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"V. Bruy\u00e8re and G. Hansel, Bertrand numeration systems and recognizability.Theoretical Computer Science181, 17\u201343 (1997).","DOI":"10.1016\/S0304-3975(96)00260-5"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"V. Bruy\u00e8re, G. Hansel, Ch. Michaux and R. Villemaire, Logic and p-recognizable sets of integers.Bull. Belg. Math. Soc. Simon Stevin1, 191\u2013238 (1994).","DOI":"10.36045\/bbms\/1103408547"},{"key":"R14","unstructured":"J.W. Cannon, D.B.A. Epstein, D.F. Holt, S.V.F. Levy, M.S. Paterson and W.P. Thurston,Word processing in groups. Jones and Barlett Publ., Boston, MA (1992)."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. Carayol and A. Meyer, Context-sensitive languages, rational graphs and determinism (2005).","DOI":"10.2168\/LMCS-2(2:6)2006"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Carayol and S. W\u00f6hrle, The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata. InFSTTCS. Lect. Notes Comput. Sci.2914, 112\u2013123 (2003).","DOI":"10.1007\/978-3-540-24597-1_10"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"O. Carton and W. Thomas, The monadic theory of morphic infinite words and generalizations.Information and Computation176, 51\u201365 (2002).","DOI":"10.1006\/inco.2001.3139"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"D. Caucal, Monadic theory of term rewritings. InLICS, pp. 266\u2013273. IEEE Computer Society (1992).","DOI":"10.1109\/LICS.1992.185539"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"D. Caucal, On infinite transition graphs having a decidable monadic theory. InICALP'96. Lect. Notes Comput. Sci.1099, 194\u2013205 (1996).","DOI":"10.1007\/3-540-61440-0_128"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"D. Caucal, On infinite terms having a decidable monadic theory. InMFCS, pp. 165\u2013176 (2002).","DOI":"10.1007\/3-540-45687-2_13"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Th. Colcombet, A combinatorial theorem for trees. InICALP'07. Lect. Notes Comput. Sci.4596, 901\u2013912 (2007).","DOI":"10.1007\/978-3-540-73420-8_77"},{"key":"R22","unstructured":"Th. Colcombet, On factorisation forests and some applications. arXiv:cs.LO\/0701113v1 (2007)."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"B. Courcelle, The monadic second-order logic of graphs ix: Machines and their behaviours.Theoretical Computer Science151, 125\u2013162 (1995).","DOI":"10.1016\/0304-3975(95)00049-3"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"B. Courcelle and I. Walukiewicz, Monadic second-order logic, graph coverings and unfoldings of transition systems.Annals of Pure and Applied Logic92, 35\u201362 (1998).","DOI":"10.1016\/S0168-0072(97)00048-1"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"C.C. Elgot and M.O. Rabin, Decidability and undecidability of extensions of second (first) order theory of (generalized) successor.Journal of Symbolic Logic31, 169\u2013181 (1966).","DOI":"10.2307\/2269808"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"S. Fratani and G. S\u00e9nizergues, Iterated pushdown automata and sequences of rational numbers.Annals of Pure and Applied Logic141, 363\u2013411, (2006).","DOI":"10.1016\/j.apal.2005.12.004"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Ch. Frougny and J. Sakarovitch, Synchronized rational relations of finite and infinite words.Theoretical Computer Science108, 45\u201382 (1993).","DOI":"10.1016\/0304-3975(93)90230-Q"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del, W. Thomas and T. Wilke, Eds.Automata, Logics, and Infinite Games. Lect. Notes Comput. Sci.2500, (2002).","DOI":"10.1007\/3-540-36387-4"},{"key":"R29","unstructured":"B.R. Hodgson, D\u00e9cidabilit\u00e9 par automate fini.Ann. Sci. Math. Qu\u00e9bec7, 39\u201357 (1983)."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"J. Honkala and M. Rigo, A note on decidability questions related to abstract numeration systems.Discrete Math.285, 329\u2013333 (2004).","DOI":"10.1016\/j.disc.2004.05.004"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"K. Culik II and J. Karhum\u00e4ki, Iterative devices generating infinite words. InSTACS '92. Lect. Notes Comput. Sci.577, 529\u2013543 (1992).","DOI":"10.1007\/3-540-55210-3_210"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"L. Kari, G. Rozenberg and A. Salomaa, L systems. InHandbook of Formal Languages, G. Rozenberg and A. Salomaa Eds.,volume I, pp. 253\u2013328. Springer, New York (1997).","DOI":"10.1007\/978-3-642-59136-5_5"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"B. Khoussainov and A. Nerode, Automatic presentations of structures. InLCC '94. Lect. Notes Comput. Sci.960, 367\u2013392 (1995).","DOI":"10.1007\/3-540-60178-3_93"},{"key":"R34","unstructured":"B. Khoussainov and S. Rubin, Automatic structures: Overview and future directions.J. Autom. Lang. Comb.8, 287\u2013301 (2003)."},{"key":"R35","unstructured":"B. Khoussainov, S. Rubin and F. Stephan, Definability and regularity in automatic structures. InSTACS '04. Lect. Notes Comput. Sci.2996, 440\u2013451 (2004)."},{"key":"R36","unstructured":"T. Lavergne, Pr\u00e9dicats alg\u00e9briques d'entiers. Rapport de stage, IRISA: Galion (2005)."},{"key":"R37","doi-asserted-by":"crossref","unstructured":"O. Ly, Automatic Graph and D0L-Sequences of Finite Graphs.Journal of Computer and System Sciences67, 497\u2013545 (2003).","DOI":"10.1016\/S0022-0000(03)00065-5"},{"key":"R38","unstructured":"A. Maes, An automata theoretic decidability proof for first-order theory of $\\langle \\mathbb{N}, <, P \\rangle$ with morphic predicateP.J. Autom. Lang. Comb.4, 229\u2013245 (1999)."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"Ch. Morvan and Ch. Rispal, Families of automata characterizing context-sensitive languages.Acta Informatica41, 293\u2013314 (2005).","DOI":"10.1007\/s00236-004-0160-0"},{"key":"R40","unstructured":"D.E. Muller and P.E. Schupp, The theory of ends, pushdown automata, and second-order logic.Theor. Comput. Sci.37, 51\u201375 (1985)."},{"key":"R41","doi-asserted-by":"crossref","unstructured":"J.-J. Pansiot, On various classes of infinite words obtained by iterated mappings. InAutomata on Infinite Words, pp. 188\u2013197 (1984).","DOI":"10.1007\/3-540-15641-0_34"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"J.-E. Pin and P.V. Silva, A topological approach to transductions.Theoretical Computer Science340, 443\u2013456 (2005).","DOI":"10.1016\/j.tcs.2005.03.029"},{"key":"R43","unstructured":"A. Rabinovich, On decidability of monadic logic of order over the naturals extended by monadic predicates. Unpublished note (2005)."},{"key":"R44","unstructured":"A. Rabinovich and W. Thomas, Decidable theories of the ordering of natural numbers with unary predicates. InCSL 2006. Lect. Notes Comput. Sci.4207, 562\u2013574 (2006)."},{"key":"R45","unstructured":"M. Rigo and A. Maes, More on generalized automatic sequences.J. Autom. Lang. Comb.7, 351\u2013376 (2002)."},{"key":"R46","doi-asserted-by":"crossref","unstructured":"Ch. Rispal, The synchronized graphs trace the context-sensistive languages.Elect. Notes Theoret. Comput. Sci.68(2002).","DOI":"10.1016\/S1571-0661(04)80533-4"},{"key":"R47","doi-asserted-by":"crossref","unstructured":"G. Rozenberg and A. Salomaa,The Book of L. Springer Verlag (1986).","DOI":"10.1007\/978-3-642-95486-3"},{"key":"R48","unstructured":"S. Rubin,Automatic Structures. Ph.D. thesis, University of Auckland, NZ (2004)."},{"key":"R49","unstructured":"S. Rubin, Automata presenting structures: A survey of the finite-string case. Manuscript."},{"key":"R50","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues, Sequences of level 1, 2, 3,..., k,... InCSR'07. Lect. Notes Comput. Sci.4649, 24\u201332 (2007).","DOI":"10.1007\/978-3-540-74510-5_6"},{"key":"R51","doi-asserted-by":"crossref","unstructured":"S. Shelah, The monadic theory of order.Annals of Mathematics102, 379\u2013419 (1975).","DOI":"10.2307\/1971037"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"L. Staiger, Rich omega-words and monadic second-order arithmetic. InCSL, pp. 478\u2013490 (1997).","DOI":"10.1007\/BFb0028032"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"W. Thomas, Languages, automata, and logic. InHandbook of Formal Languages, G. Rozenberg and A. Salomaa, Eds.,Vol. III, pp. 389\u2013455. Springer, New York (1997).","DOI":"10.1007\/978-3-642-59126-6_7"},{"key":"R54","doi-asserted-by":"crossref","unstructured":"W. Thomas, Constructing infinite graphs with a decidable mso-theory. InMFCS'03. Lect. Notes Comput. Sci.2747, 113\u2013124 (2003).","DOI":"10.1007\/978-3-540-45138-9_6"},{"key":"R55","doi-asserted-by":"crossref","unstructured":"I. Walukiewicz, Monadic second-order logic on tree-like structures.Theoretical Computer Science275, 311\u2013346 (2002).","DOI":"10.1016\/S0304-3975(01)00185-2"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2008008\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T14:42:14Z","timestamp":1738248134000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita:2008008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,3]]},"references-count":55,"journal-issue":{"issue":"3"},"alternative-id":["ita08005"],"URL":"https:\/\/doi.org\/10.1051\/ita:2008008","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6,3]]}}}