×

A hierarchy of tree-automatic structures. (English) Zbl 1241.03041

Summary: We consider \(\omega ^{n}\)-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length \(\omega ^{n}\) for some integer \(n\geq 1\). We show that all these structures are \(\omega \)-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for \(\omega ^{2}\)-automatic (resp. \(\omega ^{n}\)-automatic for \(n>2\)) Boolean algebras (respectively, partial orders, rings, commutative rings, non-commutative rings, non-commutative groups) is not determined by the axiomatic system of ZFC. We infer from the proof of the above result that the isomorphism problem for \(\omega ^{n}\)-automatic Boolean algebras, \(n\geq 2\) (respectively, rings, commutative rings, non-commutative rings, non-commutative groups) is neither a \(\Sigma^1_{2}\)-set nor a \(\Pi^1_{2}\)-set. We obtain that there exist infinitely many \(\omega ^{n}\)-automatic, hence also \(\omega \)-tree-automatic, atomless Boolean algebras \(\mathcal B_{n}\), \(n\geq 1\), which are pairwise isomorphic under the continuum hypothesis CH and pairwise non-isomorphic under an alternative axiom, AT, strengthening a result of [the authors, Cent. Eur. J. Math. 8, No. 2, 299–313 (2010; Zbl 1207.03050)].

MSC:

03C57 Computable structure theory, computable model theory
03D05 Automata and formal grammars in connection with logical questions
03E35 Consistency and independence results
03E50 Continuum hypothesis and Martin’s axiom

Citations:

Zbl 1207.03050
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] N. Bedon Finite automata and ordinals , Theoretical Computer Science , vol. 156(1996), no. 1-2, pp. 119-144. · Zbl 0871.68127
[2] —- Logic over words on denumerable ordinals , Journal of Computer and System Science , vol. 63(2001), no. 3, pp. 394-431. · Zbl 1006.68072
[3] N. Bedon and O. Carton An Eilenberg theorem for words on countable ordinals , Latin ’98: Theoretical informatics, third Latin American symposium (Claudio L. Lucchesi and Arnaldo V. Moura, editors), Lecture Notes in Computer Science, vol. 1380, Springer,1998, pp. 53-64.
[4] O. V. Belegradek The model theory of unitriangular groups , Annals of Pure and Applied Logic , vol. 68(1994), pp. 225-261. · Zbl 0807.03025
[5] A. Blumensath Automatic structures , Diploma Thesis, RWTH, Aachen,1999.
[6] A. Blumensath and E. Grädel Automatic structures , Proceedings of 15th IEEE symposium on Logic in Computer Science LICS 2000,2000, pp. 51-62.
[7] —- Finite presentations of infinite structures: Automata and interpretations , Theory of Computing Systems , vol. 37(2004), no. 6, pp. 641-674. · Zbl 1061.03038
[8] J. R. Büchi and D. Siefkes The monadic second order theory of all countable ordinals , Lecture Notes in Mathematics, vol. 328,1973. · Zbl 0298.02050
[9] J. Duparc, O. Finkel, and J.-P. Ressayre Computer science and the fine structure of Borel sets , Theoretical Computer Science , vol. 257(2001), no. 1-2, pp. 85-105. · Zbl 0971.03044
[10] I. Farah Analytic quotients: theory of liftings for quotients over analytic ideals on the integers , Memoirs of the American Mathematical Society , vol. 148(2000). · Zbl 0966.03045
[11] —- Luzin gaps , Transactions of the American Mathematical Society , vol. 356(2004), no. 6, pp. 2197-2239, (electronic). · Zbl 1046.03031
[12] —- All automorphism of the Calkin algebras are inner , Annals of Mathematics , vol. 173(2011), no. 2, pp. 619-661. · Zbl 1250.03094
[13] O Finkel Locally finite languages , Theoretical Computer Science , vol. 255(2001), no. 1-2, pp. 223-261. · Zbl 0974.68096
[14] O. Finkel and S. Todorčević The isomorphism relation between tree-automatic structures , Central European Journal of Mathematics , vol. 8(2010), no. 2, pp. 299-313. · Zbl 1207.03050
[15] E. Grädel, W. Thomas, and W. Wilke (editors) Automata, logics, and infinite games: A guide to current research , Lecture Notes in Computer Science, vol. 2500, Springer,2002. · Zbl 1011.00037
[16] J. C. Hemmer Automates sur mots de longueur supérieure á \(\omega\) , Mémoire de Licence, Université de Liège,1992.
[17] G. Hjorth, B. Khoussainov, A. Montalbán, and A. Nies From automatic structures to Borel structures , Proceedings of the twenty-third annual IEEE symposium on Logic in Computer Science, LICS 2008, IEEE Computer Society, Pittsburgh, PA,2008, pp. 431-441.
[18] B. R. Hodgson Décidabilité par automate fini , Annales Scientifiques de Mathématiques du Québec , vol. 7(1983), no. 1, pp. 39-57. · Zbl 0531.03007
[19] J. E. Hopcroft, R. Motwani, and J. D. Ullman Introduction to automata theory, languages, and computation , Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Co., Reading, Mass.,2001. · Zbl 0980.68066
[20] T. Jech Set theory , third ed., Springer,2002.
[21] W. Just A modification of Shelah’s oracle-c.c. with applications , Transactions of the American Mathematical Society , vol. 329(1992), no. 1, pp. 325-356. · Zbl 0753.03021
[22] —- A weak version of \(\text{\upshape AT}\) from \(\text{\upshape OCA}\), Set theory of the continuum , Mathematical Sciences Research Institute Publications, vol. 26, Springer,1992, pp. 281-291.
[23] V. Kanovei and M. Reeken New Radon-Nikodym ideals , Mathematika , vol. 47(2000), no. 1-2, pp. 219-227. · Zbl 1025.03045
[24] A. S. Kechris Classical descriptive set theory , Springer-Verlag, New York,1995.
[25] B. Khoussainov and A. Nerode Open questions in the theory of automatic structures , Bulletin of the European Association of Theoretical Computer Science , vol. 94(2008), pp. 181-204. · Zbl 1169.03352
[26] B. Khoussainov, A. Nies, S. Rubin, and F. Stephan Automatic structures: Richness and limitations , Logical Methods in Computer Science , vol. 3(2007), no. 2, pp. 1-18. · Zbl 1128.03028
[27] B. Khoussainov and S. Rubin Automatic structures: Overview and future directions , Journal of Automata, Languages and Combinatorics , vol. 8(2003), no. 2, pp. 287-301. · Zbl 1058.68070
[28] D. Kuske Is Ramsey’s Theorem omega-automatic? , 27th International Symposium on Theoretical Aspects of Computer Science , STACS 2010, Leibniz International Proceedings in Computer Science, vol. 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,2010, pp. 537-548. · Zbl 1230.03067
[29] D. Kuske, J. Liu, and M. Lohrey The isomorphism problem for omega -automatic trees , Proceedings of Computer Science Logic , CSL 2010, Lecture Notes in Computer Science, vol. 6247, Springer,2010, pp. 396-410. · Zbl 1287.03084
[30] —- The isomorphism problem on classes of automatic structures , Proceedings of the 25th annual IEEE symposium on Logic in Computer Science, LICS 2010, IEEE Computer Society,2010, pp. 160-169.
[31] D. Kuske and M. Lohrey First-order and counting theories of omega-automatic structures , Journal of Symbolic Logic, vol. 73(2008), no. 1, pp. 129-150. · Zbl 1141.03015
[32] Y. N. Moschovakis Descriptive set theory , North-Holland Publishing Co., Amsterdam,1980.
[33] A. Nies Describing groups , Bulletin of Symbolic Logic, vol. 13(2007), no. 3, pp. 305-339. · Zbl 1167.20017
[34] D. Perrin and J.-E. Pin Infinite words, automata, semigroups, logic and games , Pure and Applied Mathematics, vol. 141, Elsevier,2004. · Zbl 1094.68052
[35] B. Poizat A course in model theory , Universitext, Springer-Verlag, New York,2000.
[36] M. O. Rabin Decidability of second-order theories and automata on infinite trees , Transactions of the American Mathematical Society , vol. 141(1969), pp. 1-35. · Zbl 0221.02031
[37] B. Rotman A mapping theorem for countable well-ordered sets , Journal of the London Mathematical Society. Second Series , vol. 2(1970), pp. 509-512. · Zbl 0212.02203
[38] S. Rubin Automatic structures , Ph.D. thesis, University of Auckland,2004. · Zbl 1122.68466
[39] —- Automata presenting structures: A survey of the finite string case , Bulletin of Symbolic Logic, vol. 14(2008), no. 2, pp. 169-209. · Zbl 1146.03028
[40] L. Staiger \(\omega\)-languages , Handbook of formal languages , vol. 3, Springer, Berlin,1997, pp. 339-387.
[41] M. Talagrand Compacts de fonctions mesurables et filtres non mesurables , Studia Mathematica , vol. 67(1980), no. 1, pp. 13-43. · Zbl 0435.46023
[42] W. Thomas Automata on infinite objects , Handbook of theoretical computer science (J. van Leeuwen, editor), Formal models and semantics, vol. B, Elsevier,1990, pp. 135-191. · Zbl 0900.68316
[43] S. Todorčević Partition problems in topology , Contemporary Mathematics, vol. 84, American Mathematical Society, Providence, R.I.,1989. · Zbl 0659.54001
[44] —- Gaps in analytic quotients , Fundamenta Mathematicae , vol. 156(1998), no. 1, pp. 85-97.
[45] J. Wojciechowski Classes of transfinite sequences accepted by finite automata , Fundamenta Informaticae , vol. 7(1984), no. 2, pp. 191-223. · Zbl 0553.68048
[46] —- Finite automata on transfinite sequences and regular expressions , Fundamenta Informaticae , vol. 8(1985), no. 3-4, pp. 379-396. · Zbl 0573.68045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.