  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.
