An ω-tree-automatic structure is a relational structure whose domain and relations are accepted by Muller or Rabin tree automata. We investigate in this paper the isomorphism problem for ω-tree-automatic structures. We prove first that the isomorphism relation for ω-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n ≥ 2) is not determined by the axiomatic system ZFC. Then we prove that the isomorphism problem for ω-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n ≥ 2) is neither a Σ21-set nor a Π21-set.
@article{bwmeta1.element.doi-10_2478_s11533-010-0014-7,
author = {Olivier Finkel and Stevo Todor\v cevi\'c},
title = {The isomorphism relation between tree-automatic Structures},
journal = {Open Mathematics},
volume = {8},
year = {2010},
pages = {299-313},
zbl = {1207.03050},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0014-7}
}
Olivier Finkel; Stevo Todorčević. The isomorphism relation between tree-automatic Structures. Open Mathematics, Tome 8 (2010) pp. 299-313. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0014-7/
[1] Bárány V., Kaiser L., Rubin S., Cardinality and counting quantifiers on omega-automatic structures, In: Albers S., Weil P. (Eds.), STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21–23, 2008, Proceedings, Dagstuhl Seminar Proceedings, 2008, 08001, 385–396 | Zbl 1259.68109
[2] Belegradek O.V., The model theory of unitriangular groups, Annals of Pure and Applied Logic, 1994, 68, 225–261 http://dx.doi.org/10.1016/0168-0072(94)90022-1
[3] Blumensath A., Automatic Structures, Diploma Thesis, RWTH Aachen, 1999
[4] Blumensath A., Grädel E., Finite presentations of infinite structures: Automata and interpretations, Theory of Computing Systems, 2004, 37(6), 641–674 http://dx.doi.org/10.1007/s00224-004-1133-y | Zbl 1061.03038
[5] Delhommé C., Automaticité des ordinaux et des graphes homogènes, Comptes Rendus de L’Académie des Sciences, Mathématiques, 2004, 339(1), 5–10 (in French)
[6] Farah I., Analytic quotients: theory of liftings for quotients over analytic ideals on the integers, Memoirs of the American Mathematical Society, 2000, 148 | Zbl 0966.03045
[7] Hjorth G., Khoussainov B., Montalbán A., Nies A., From automatic structures to Borel structures, In: Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24–27 June 2008, Pittsburgh, PA, USA, 2008, IEEE Computer Society, 431–441
[8] Hodgson B. R., Décidabilité par automate fini, Annales Scientifiques de Mathématiques du Québec, 1983, 7(1), 39–57 (in French) | Zbl 0531.03007
[9] Jech T., Set theory, third edition, Springer, 2002
[10] Just W., A weak version of AT from OCA, In: Set theory of the continuum (Berkeley, CA, 1989), Math. Sci. Res. Inst. Publ., 26, Springer, New York, 1992
[11] Just W., Krawczyk A., On certain Boolean algebras P(ω)/I, Transactions of the American Mathematical Society, 1984, 285(1), 411–429 http://dx.doi.org/10.2307/1999489 | Zbl 0519.06011
[12] Kechris A.S., Classical descriptive set theory, Springer-Verlag, New York, 1995 | Zbl 0819.04002
[13] Khoussainov B., Nies A., Rubin S., Stephan F., Automatic structures: Richness and limitations, Logical Methods in Computer Science, 2007, 3(2), 1–18 http://dx.doi.org/10.2168/LMCS-3(2:2)2007 | Zbl 1128.03028
[14] Khoussainov B., Rubin S., Automatic structures: Overview and future directions, Journal of Automata, Languages and Combinatorics, 2003, 8(2), 287–301 | Zbl 1058.68070
[15] Kuske D., Lohrey M., First-order and counting theories of omega-automatic structures, Journal of Symbolic Logic, 2008, 73, 129–150 http://dx.doi.org/10.2178/jsl/1208358745 | Zbl 1141.03015
[16] Lescow H., Thomas W., Logical specifications of infinite computations, In: de Bakker J.W., de Roever W.P., Rozenberg G. (Eds.), A decade of concurrency, Lecture Notes in Computer Science, 1994, 803, 583–621
[17] Moschovakis Y.N., Descriptive set theory, North-Holland Publishing Co., Amsterdam, 1980 | Zbl 0433.03025
[18] Nies A., Describing groups, Bulletin of Symbolic Logic, 2007, 13(3), 305–339 http://dx.doi.org/10.2178/bsl/1186666149
[19] Perrin D., Pin J.-E., Infinite words, automata, semigroups, logic and games, Pure and Applied Mathematics, 2004, 141 | Zbl 1094.68052
[20] Rubin S., Automatic Structuresm, PhD thesis, University of Auckland, 2004
[21] Rubin S., Automata presenting structures: A survey of the finite string case, Bulletin of Symbolic Logic, 2008, 14(2), 169–209 http://dx.doi.org/10.2178/bsl/1208442827 | Zbl 1146.03028
[22] Staiger L., ω-languages, In: Handbook of formal languages, Springer, Berlin, 1997, 3, 339–387
[23] Thomas W., Automata on infinite objects, In: van Leeuwen J. (Ed.), Handbook of theoretical computer science, Formal models and semantics, Elsevier, 1990, B, 135–191
[24] Todorčcević S., Partition problems in topology, Contemporary Mathematics, vol. 84, American Mathematical Society, Providence, R.I., 1989
[25] Todorčević S., Gaps in analytic quotients, Fundamenta Mathematicae, 1998, 156(1), 85–97 | Zbl 0906.03048