  The main result of this paper is that the isomorphism for omega-automatic
trees of finite height is at least has hard as second-order arithmetic and
therefore not analytical. This strengthens a recent result by Hjorth,
Khoussainov, Montalban, and Nies showing that the isomorphism problem for
omega-automatic structures is not $\Sigma^1_2$. Moreover, assuming the
continuum hypothesis CH, we can show that the isomorphism problem for
omega-automatic trees of finite height is recursively equivalent with
second-order arithmetic. On the way to our main results, we show lower and
upper bounds for the isomorphism problem for omega-automatic trees of every
finite height: (i) It is decidable ($\Pi^0_1$-complete, resp,) for height 1 (2,
resp.), (ii) $\Pi^1_1$-hard and in $\Pi^1_2$ for height 3, and (iii)
$\Pi^1_{n-3}$- and $\Sigma^1_{n-3}$-hard and in $\Pi^1_{2n-4}$ (assuming CH)
for all n > 3. All proofs are elementary and do not rely on theorems from set
theory.
