The Isomorphism Problem for omega-Automatic Trees

Abstract

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 }_2^1$. 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 }_1^0$-complete, resp,) for height 1 (2, resp.), (ii) ${\Pi }_1^1$-hard and in ${\Pi }_2^1$ for height 3, and (iii) ${\Pi }_{n-3}^1$- and ${\Sigma }_{n-3}^1$-hard and in ${\Pi }_{2n-4}^1$ (assuming CH) for all n > 3. All proofs are elementary and do not rely on theorems from set theory.