{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T07:59:52Z","timestamp":1777449592706,"version":"3.51.4"},"reference-count":46,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":741,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider<jats:italic>\u03c9<jats:sup>n<\/jats:sup><\/jats:italic>-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length<jats:italic>\u03c9<jats:sup>n<\/jats:sup><\/jats:italic>for some integer<jats:italic>n<\/jats:italic>\u2265 1. We show that all these structures are<jats:italic>\u03c9<\/jats:italic>-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for<jats:italic>\u03c9<\/jats:italic><jats:sup>2<\/jats:sup>-automatic (resp.<jats:italic>\u03c9<jats:sup>n<\/jats:sup><\/jats:italic>-automatic for<jats:italic>n<\/jats:italic>&gt; 2) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem for<jats:italic>\u03c9<jats:sup>n<\/jats:sup><\/jats:italic>-automatic boolean algebras,<jats:italic>n<\/jats:italic>\u2265 2, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200001080_inline1\"\/>-set nor a<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200001080_inline2\"\/>-set. We obtain that there exist infinitely many<jats:italic>\u03c9<jats:sup>n<\/jats:sup><\/jats:italic>-automatic, hence also<jats:italic>\u03c9<\/jats:italic>-tree-automatic, atomless boolean algebras<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200001080_inline3\"\/>, which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [14].<\/jats:p>","DOI":"10.2178\/jsl\/1327068708","type":"journal-article","created":{"date-parts":[[2012,1,20]],"date-time":"2012-01-20T14:16:13Z","timestamp":1327068973000},"page":"350-368","source":"Crossref","is-referenced-by-count":5,"title":["A hierarchy of tree-automatic structures"],"prefix":"10.1017","volume":"77","author":[{"given":"Olivier","family":"Finkel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stevo","family":"Todor\u010devi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200001080_ref045","doi-asserted-by":"crossref","first-page":"191","DOI":"10.3233\/FI-1984-7203","article-title":"Classes of transfinite sequences accepted by finite automata","volume":"7","author":"Wojciechowski","year":"1984","journal-title":"Fundamenta Informaticae"},{"key":"S0022481200001080_ref043","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/084"},{"key":"S0022481200001080_ref041","doi-asserted-by":"publisher","DOI":"10.4064\/sm-67-1-13-43"},{"key":"S0022481200001080_ref037","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/2.Part_3.509"},{"key":"S0022481200001080_ref031","first-page":"129","volume":"73","author":"Kuske","year":"2008","journal-title":"First-order and counting theories of omega-automatic structures"},{"key":"S0022481200001080_ref029","first-page":"396","volume-title":"Proceedings of Computer Science Logic, CSL 2010","volume":"6247","author":"Kuske","year":"2010"},{"key":"S0022481200001080_ref028","first-page":"537","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010","volume":"5","author":"Kuske","year":"2010"},{"key":"S0022481200001080_ref027","first-page":"287","article-title":"Automatic structures: Overview and future directions","volume":"8","author":"Khoussainov","year":"2003","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0022481200001080_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4190-4"},{"key":"S0022481200001080_ref020","volume-title":"Set theory","author":"Jech","year":"2002"},{"key":"S0022481200001080_ref019","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft","year":"2001"},{"key":"S0022481200001080_ref016","volume-title":"Automates sur mots de longueur sup\u00e9rieure \u00e1","author":"Hemmer","year":"1992"},{"key":"S0022481200001080_ref010","doi-asserted-by":"publisher","DOI":"10.1090\/memo\/0702"},{"key":"S0022481200001080_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00111-0"},{"key":"S0022481200001080_ref008","volume":"328","author":"B\u00e3\u226bChi","year":"1973","journal-title":"The monadic second order theory of all countable ordinals"},{"key":"S0022481200001080_ref006","first-page":"51","volume-title":"Proceedings of 15th IEEE symposium on Logic in Computer Science LICS 2000","author":"Blumensath","year":"2000"},{"key":"S0022481200001080_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)90022-1"},{"key":"S0022481200001080_ref042","first-page":"135","volume-title":"Handbook of theoretical computer science","volume":"B","author":"Thomas","year":"1990"},{"key":"S0022481200001080_ref005","unstructured":"Blumensath A. , Automatic structures, Diploma Thesis, RWTH, Aachen, 1999."},{"key":"S0022481200001080_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9754-0_17"},{"key":"S0022481200001080_ref002","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1782"},{"key":"S0022481200001080_ref011","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-04-03565-2"},{"key":"S0022481200001080_ref034","volume-title":"Infinite words, automata, semigroups, logic and games","volume":"141","author":"Perrin","year":"2004"},{"key":"S0022481200001080_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36387-4"},{"key":"S0022481200001080_ref025","first-page":"181","article-title":"Open questions in the theory of automatic structures","volume":"94","author":"Khoussainov","year":"2008","journal-title":"Bulletin of the European Association of Theoretical Computer Science"},{"key":"S0022481200001080_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00006-2"},{"key":"S0022481200001080_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00286-8"},{"key":"S0022481200001080_ref039","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1208442827"},{"key":"S0022481200001080_ref038","unstructured":"Rubin S. , Automatic structures, Ph.D. thesis, University of Auckland, 2004."},{"key":"S0022481200001080_ref026","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(2:2)2007"},{"key":"S0022481200001080_ref023","doi-asserted-by":"publisher","DOI":"10.1112\/S0025579300015837"},{"key":"S0022481200001080_ref017","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.28"},{"key":"S0022481200001080_ref033","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1186666149"},{"key":"S0022481200001080_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1133-y"},{"key":"S0022481200001080_ref014","doi-asserted-by":"publisher","DOI":"10.2478\/s11533-010-0014-7"},{"key":"S0022481200001080_ref040","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_6"},{"key":"S0022481200001080_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054310"},{"key":"S0022481200001080_ref044","doi-asserted-by":"crossref","first-page":"85","DOI":"10.4064\/fm-156-1-85-97","article-title":"Gaps in analytic quotients","volume":"156","author":"Todor\u010devi\u0107","year":"1998","journal-title":"Fundamenta Mathematicae"},{"key":"S0022481200001080_ref036","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":"S0022481200001080_ref018","first-page":"39","article-title":"D\u00e9cidabilit\u00e9 par automate fini","volume":"7","author":"Hodgson","year":"1983","journal-title":"Anuales Scientifiques de Math\u00e9matiques du Quebec"},{"key":"S0022481200001080_ref035","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8622-1"},{"key":"S0022481200001080_ref021","first-page":"325","article-title":"A modification of Shelah's oracle-c.c. with applications","volume":"329","author":"Just","year":"1992","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200001080_ref046","doi-asserted-by":"crossref","first-page":"379","DOI":"10.3233\/FI-1985-83-407","article-title":"Finite automata on transfinite sequences and regular expressions","volume":"8","author":"Wojciechowski","year":"1985","journal-title":"Fundamenta Informaticae"},{"key":"S0022481200001080_ref032","volume-title":"Descriptive set theory","author":"Moschovakis","year":"1980"},{"key":"S0022481200001080_ref030","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.10"},{"key":"S0022481200001080_ref012","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2011.173.2.1"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200001080","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T21:49:41Z","timestamp":1686692981000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200001080\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["S0022481200001080"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1327068708","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}