The isomorphism relation between tree-automatic Structures

• Autorzy: Olivier Finkel , Stevo Todorčević
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

ω-tree-automatic structures; Boolean algebras; Partial orders; Rings; Groups; Isomorphism relation; Models of set theory; Independence results

Kategorie tematyczne

• 03B70: Logic in computer science
• 03C52: Properties of classes of models
• 03D05: Automata and formal grammars in connection with logical questions
• 03E35: Consistency and independence results

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2010
• Tom: 8
• Numer: 2
• Strony: 299-313

Daty

wydano

2010-04-01

online

2010-04-14

Twórcy

autor

Olivier Finkel

• CNRS and Université Paris 7

autor

Stevo Todorčević

Bibliografia

• [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
• [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
• [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
• [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)
• [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
• [12] Kechris A.S., Classical descriptive set theory, Springer-Verlag, New York, 1995
• [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
• [14] Khoussainov B., Rubin S., Automatic structures: Overview and future directions, Journal of Automata, Languages and Combinatorics, 2003, 8(2), 287–301
• [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
• [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
• [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
• [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
• [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

Identyfikatory

DOI

10.2478/s11533-010-0014-7