The isomorphism relation between tree-automatic structures

DOI10.2478/S11533-010-0014-7MaRDI QIDQ707994zbMATH OpenOpenAlexFDO

Authors Olivier Finkel, Stevo Todorčević

Publication date 8 October 2010

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 1192335 (Why is no real title available?)
• scientific article; zbMATH DE number 48095 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 2040323 (Why is no real title available?)
• scientific article; zbMATH DE number 218620 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• Analytic quotients: theory of liftings for quotients over analytic ideals on the integers
• Automata Presenting Structures: A Survey of the Finite String Case
• Automatic Structures: Richness and Limitations
• Automaticity of ordinals and of homogeneous graphs
• Cardinality and counting quantifiers on omega-automatic structures
• Describing Groups
• Descriptive set theory
• Finite presentations of infinite structures: Automata and interpretations
• First-order and counting theories ofω-automatic structures
• On Certain Boolean Algebras P(ω)/I
• Partition Problems in Topology
• Set Theory
• The model theory of unitriangular groups

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)