The isomorphism problem on classes of automatic structures with transitive relations (Q2847190)

In this paper, the authors study the isomorphism problem on classes of automatic structures (finitely presented structures where the universe and all relations can be recognized by finite automata). They prove that the isomorphism problem for automatic equivalence structures is \(\Pi_1^0\)-complete; the isomorphism problem for automatic order trees and linear orders is \(\Sigma_1^1\)-complete; the isomorphism problem for automatic well-founded order trees and automatic trees of bounded height is recursively equivalent to first-order arithmetic; the isomorphism problem for automatic trees of height \(n\geq 2\) is \(\Pi_{2n-3}^0\)-complete. The authors also show that the isomorphism problem for scattered linear orders can be reduced to true arithmetic, but leave open the question on the lower bound for this problem.