Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Isomorphism Relation Between Tree-Automatic Structures
170
0
0.0
(
0
)
Added by
Olivier Finkel
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Authors
Olivier Finkel
Ask ChatGPT about the research
No Arabic 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 $Sigma_2^1$-set nor a $Pi_2^1$-set.
rate research
Read More
We consider $omega^n$-automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length $omega^n$ for some integer $ngeq 1$. 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 $omega^2$-automatic (resp. $omega^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 $omega^n$-automatic boolean algebras, $n > 1$, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a $Sigma_2^1$-set nor a $Pi_2^1$-set. We obtain that there exist infinitely many $omega^n$-automatic, hence also $omega$-tree-automatic, atomless boolean algebras $B_n$, $ngeq 1$, which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [FT10].
We prove that the injectively omega-tree-automatic ordinals are the ordinals smaller than $omega^{omega^omega}$. Then we show that the injectively $omega^n$-automatic ordinals, where $n>0$ is an integer, are the ordinals smaller than $omega^{omega^n}$. This strengthens a recent result of Schlicht and Stephan who considered in [Schlicht-Stephan11] the subclasses of finite word $omega^n$-automatic ordinals. As a by-product we obtain that the hierarchy of injectively $omega^n$-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.
This paper studies tree-automatic ordinals (or equivalently, well-founded linearly ordered sets) together with the ordinal addition operation +. Informally, these are ordinals such that their elements are coded by finite trees for which the linear order relation of the ordinal and the ordinal addition operation can be determined by tree automata. We describe an algorithm that, given two tree-automatic ordinals with the ordinal addition operation, decides if the ordinals are isomorphic.
A general theme of computable structure theory is to investigate when structures have copies of a given complexity $Gamma$. We discuss such problem for the case of equivalence structures and preorders. We show that there is a $Pi^0_1$ equivalence structure with no $Sigma^0_1$ copy, and in fact that the isomorphism types realized by the $Pi^0_1$ equivalence structures coincide with those realized by the $Delta^0_2$ equivalence structures. We also construct a $Sigma^0_1$ preorder with no $Pi^0_1$ copy.
We study the existence of automatic presentations for various algebraic structures. An automatic presentation of a structure is a description of the universe of the structure by a regular set of words, and the interpretation of the relations by synchronised automata. Our first topic concerns characterising classes of automatic structures. We supply a characterisation of the automatic Boolean algebras, and it is proven that the free Abelian group of infinite rank, as well as certain Fraisse limits, do not have automatic presentations. In particular, the countably infinite random graph and the random partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. Our second topic is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is Sigma_1^1-complete.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
