• The isomorphism problem for ω-automatic trees

      Kuske, D; Liu, J; Lohrey, M (Springer Berlin / Heidelberg, 2010)
      The main result of this paper is that the isomorphism problem for ω-automatic trees of finite height is at least as hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, ...
    • The isomorphism problem on classes of automatic structures

      Kuske, D; Liu, J; Lohrey, M (IEEE Computer Society, 2010)
      Several new undecidability results on isomorphism problems for automatic structures are shown: (i) The isomorphism problem for automatic equivalence relations is \Pi^0_1-complete, (ii) The isomorphism problem for automatic ...