The Isomorphism Problem On Classes of Automatic Structures

Details The Isomorphism Problem On Classes of Automatic Structures The Isomorphism Problem On Classes of Automatic Structures

2010-01-13

arxiv.org/abs/1001.2086v1

Computer Science

Logic in Computer Science

Scientific paper

Automatic structures are finitely presented structures where the universe and all relations can be recognized by finite automata. It is known that the isomorphism problem for automatic structures is complete for $\Sigma^1_1$; the first existential level of the analytical hierarchy. Several new results on isomorphism problems for automatic structures are shown in this paper: (i) The isomorphism problem for automatic equivalence relations is complete for $\Pi^0_1$ (first universal level of the arithmetical hierarchy). (ii) The isomorphism problem for automatic trees of height $n \geq 2$ is $\Pi^0_{2n-3}$-complete. (iii) The isomorphism problem for automatic linear orders is not arithmetical. This solves some open questions of Khoussainov, Rubin, and Stephan.

Affiliated with

Also associated with

No associations

Rating

The Isomorphism Problem On Classes of 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 Problem On Classes of Automatic Structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Isomorphism Problem On Classes of Automatic Structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-524932