The isomorphism relation between tree-automatic structures

DOI10.2478/S11533-010-0014-7zbMATH Open1207.03050arXiv1007.0822OpenAlexW3103414753MaRDI QIDQ707994FDOQ707994

Authors: Olivier Finkel, Stevo Todorčević 

Publication date: 8 October 2010

Published in: Central European Journal of Mathematics (Search for Journal in Brave)

Abstract: An $omega$-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 $omega$-tree-automatic structures. We prove first that the isomorphism relation for $omega$-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n >1) is not determined by the axiomatic system ZFC. Then we prove that the isomorphism problem for $omega$-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n >1) is neither a $Sigm{a}_2^1$-set nor a $P{i}_2^1$-set.

Full work available at URL: https://arxiv.org/abs/1007.0822

Recommendations

• A hierarchy of tree-automatic structures
• The isomorphism problem on classes of automatic structures with transitive relations
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for tree-automatic ordinals with addition

zbMATH Keywords

partial ordersisomorphism problemtree automataBoolean algebrasmodels of set theoryrelational structureindependence results\(\omega \)-tree-automatic structures

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15) Properties of classes of models (03C52) Models of arithmetic and set theory (03C62)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Automaticity of ordinals and of homogeneous graphs
• Title not available (Why is that?)
• Automata Presenting Structures: A Survey of the Finite String Case
• Set Theory
• Automatic Structures: Richness and Limitations
• Descriptive set theory
• On Certain Boolean Algebras P(ω)/I
• Analytic quotients: theory of liftings for quotients over analytic ideals on the integers
• Title not available (Why is that?)
• Partition Problems in Topology
• Title not available (Why is that?)
• Describing Groups
• Title not available (Why is that?)
• First-order and counting theories ofω-automatic structures
• The model theory of unitriangular groups
• Title not available (Why is that?)
• Finite presentations of infinite structures: Automata and interpretations
• Title not available (Why is that?)
• Cardinality and counting quantifiers on omega-automatic structures

Cited In (7)

• Deciding Parity Games in Quasi-polynomial Time
• A hierarchy of tree-automatic structures
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for \(\omega \)-automatic trees
• The big-O problem
• Deciding the isomorphism problem in classes of unary automatic structures
• The isomorphism problem on classes of automatic structures with transitive relations

This page was built for publication: The isomorphism relation between tree-automatic structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q707994)