A hierarchy of tree-automatic structures

DOI10.2178/JSL/1327068708MaRDI QIDQ5388735zbMATH OpenOpenAlexFDO

Authors Stevo Todorčević, Olivier Finkel

Publication date 19 April 2012

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1504, https://projecteuclid.org/euclid.jsl/1327068708

zbMATH Keywords

models of set theoryindependence results\(\omega \)-tree-automatic structuresisomorphism relation\(\omega ^{n}\)-automatic structuresautomata reading ordinal words

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57) Consistency and independence results (03E35) Continuum hypothesis and Martin's axiom (03E50)

Abstract: We consider $omeg{a}^n$-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length $omeg{a}^n$ for some integer $ngeq1$. We show that all these structures are $omega$-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for $omeg{a}^2$-automatic (resp. $omeg{a}^n$-automatic for $n>2$) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem for $omeg{a}^n$-automatic boolean algebras, $n>1$, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a $Sigm{a}_2^1$-set nor a $P{i}_2^1$-set. We obtain that there exist infinitely many $omeg{a}^n$-automatic, hence also $omega$-tree-automatic, atomless boolean algebras $B_n$, $ngeq1$, which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [FT10].

Recommendations

• The isomorphism relation between tree-automatic structures
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem on classes of automatic structures with transitive relations
• Automatic Structures: Richness and Limitations

Cites work

• scientific article; zbMATH DE number 3881897 (Why is no real title available?)
• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 5605134 (Why is no real title available?)
• scientific article; zbMATH DE number 3915652 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 2040323 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• A Modification of Shelah's Oracle-C.C. with Applications
• All automorphisms of the Calkin algebra are inner
• Analytic quotients: theory of liftings for quotients over analytic ideals on the integers
• Automata Presenting Structures: A Survey of the Finite String Case
• Automata, logics, and infinite games. A guide to current research
• Automatic Structures: Richness and Limitations
• Compacts de fonctions mesurables et filtres non mesurables
• Computer science and the fine structure of Borel sets
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Describing Groups
• Finite automata and ordinals
• Finite presentations of infinite structures: Automata and interpretations
• First-order and counting theories ofω-automatic structures
• Is Ramsey's theorem omega-automatic?
• Locally finite languages
• Logic over words on denumerable ordinals
• Luzin gaps
• New Radon–Nikodym ideals
• On Countable Indecomposable Order Types
• Partition Problems in Topology
• STACS 2004
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism relation between tree-automatic structures
• The model theory of unitriangular groups
• The monadic second order theory of all countable ordinals

Cited in

(10)

• Tree-automatic scattered linear orders
• Deciding Parity Games in Quasi-polynomial Time
• Pumping for ordinal-automatic structures1
• The isomorphism relation between tree-automatic structures
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for \(\omega \)-automatic trees
• Aggregation tree construction using hierarchical structures
• The isomorphism problem for tree-automatic ordinals with addition
• scientific article; zbMATH DE number 7444022 (Why is no real title available?)
• scientific article; zbMATH DE number 1136080 (Why is no real title available?)

This page was built for publication: A hierarchy of tree-automatic structures

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