The isomorphism relation between tree-automatic Structures

Olivier Finkel; Stevo Todorčević

Open Mathematics (2010)

  • Volume: 8, Issue: 2, page 299-313
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Olivier Finkel, and Stevo Todorčević. "The isomorphism relation between tree-automatic Structures." Open Mathematics 8.2 (2010): 299-313. <http://eudml.org/doc/269261>.

@article{OlivierFinkel2010,
abstract = {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.},
author = {Olivier Finkel, Stevo Todorčević},
journal = {Open Mathematics},
keywords = {ω-tree-automatic structures; Boolean algebras; Partial orders; Rings; Groups; Isomorphism relation; Models of set theory; Independence results; -tree-automatic structures; partial orders; models of set theory; independence results; relational structure; tree automata; isomorphism problem},
language = {eng},
number = {2},
pages = {299-313},
title = {The isomorphism relation between tree-automatic Structures},
url = {http://eudml.org/doc/269261},
volume = {8},
year = {2010},
}

TY - JOUR
AU - Olivier Finkel
AU - Stevo Todorčević
TI - The isomorphism relation between tree-automatic Structures
JO - Open Mathematics
PY - 2010
VL - 8
IS - 2
SP - 299
EP - 313
AB - 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.
LA - eng
KW - ω-tree-automatic structures; Boolean algebras; Partial orders; Rings; Groups; Isomorphism relation; Models of set theory; Independence results; -tree-automatic structures; partial orders; models of set theory; independence results; relational structure; tree automata; isomorphism problem
UR - http://eudml.org/doc/269261
ER -

References

top
  1. [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 Zbl1259.68109
  2. [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. [3] Blumensath A., Automatic Structures, Diploma Thesis, RWTH Aachen, 1999 
  4. [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 Zbl1061.03038
  5. [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. [6] Farah I., Analytic quotients: theory of liftings for quotients over analytic ideals on the integers, Memoirs of the American Mathematical Society, 2000, 148 Zbl0966.03045
  7. [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. [8] Hodgson B. R., Décidabilité par automate fini, Annales Scientifiques de Mathématiques du Québec, 1983, 7(1), 39–57 (in French) Zbl0531.03007
  9. [9] Jech T., Set theory, third edition, Springer, 2002 
  10. [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. [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 Zbl0519.06011
  12. [12] Kechris A.S., Classical descriptive set theory, Springer-Verlag, New York, 1995 Zbl0819.04002
  13. [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 Zbl1128.03028
  14. [14] Khoussainov B., Rubin S., Automatic structures: Overview and future directions, Journal of Automata, Languages and Combinatorics, 2003, 8(2), 287–301 Zbl1058.68070
  15. [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 Zbl1141.03015
  16. [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. [17] Moschovakis Y.N., Descriptive set theory, North-Holland Publishing Co., Amsterdam, 1980 Zbl0433.03025
  18. [18] Nies A., Describing groups, Bulletin of Symbolic Logic, 2007, 13(3), 305–339 http://dx.doi.org/10.2178/bsl/1186666149 
  19. [19] Perrin D., Pin J.-E., Infinite words, automata, semigroups, logic and games, Pure and Applied Mathematics, 2004, 141 Zbl1094.68052
  20. [20] Rubin S., Automatic Structuresm, PhD thesis, University of Auckland, 2004 
  21. [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 Zbl1146.03028
  22. [22] Staiger L., ω-languages, In: Handbook of formal languages, Springer, Berlin, 1997, 3, 339–387 
  23. [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. [24] Todorčcević S., Partition problems in topology, Contemporary Mathematics, vol. 84, American Mathematical Society, Providence, R.I., 1989 
  25. [25] Todorčević S., Gaps in analytic quotients, Fundamenta Mathematicae, 1998, 156(1), 85–97 Zbl0906.03048

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.