Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników


2010 | 8 | 2 | 299-313

Tytuł artykułu

The isomorphism relation between tree-automatic Structures

Treść / Zawartość

Warianty tytułu

Języki publikacji



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.


  • [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
  • [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
  • [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
  • [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
  • [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
  • [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
  • [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
  • [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

Typ dokumentu



Identyfikator YADDA

JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.