The Isomorphism Relation Between Tree-Automatic Structures

Details The Isomorphism Relation Between Tree-Automatic Structures The Isomorphism Relation Between Tree-Automatic Structures

2010-07-06

arxiv.org/abs/1007.0822v1

Central European Journal of Mathematics 8, 2 (2010) p. 299-313

Mathematics

Logic

Scientific paper

10.2478/s11533-010-0014-7

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.

Affiliated with

Also associated with

No associations

Rating

The Isomorphism Relation Between Tree-Automatic Structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Isomorphism Relation Between Tree-Automatic Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Isomorphism Relation Between Tree-Automatic Structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-216323