• 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 ...
    • Tree-automatic well-founded trees

      Liu, J; Kartzow, A; Lohrey, M; Huschenbett, M (International Federation of Computational Logic, 2013)
      We investigate tree-automatic well-founded trees. Using Delhomme's decomposition technique for tree-automatic structures, we show that the (ordinal) rank of a tree-automatic well-founded tree is strictly below omega^omega. ...