The Isomorphism Problem for omega-Automatic Trees

2010/04/05 by Dietrich Kuske, Jiamou Liu, Kuske, Dietrich +3
Computer Science · Mathematics · #03C57 #03D05 #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1004.0610

openalex publication_date 2010/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Σ¹₂. 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 (Π⁰₁-complete, resp,) for height 1 (2, resp.), (ii) Π¹₁-hard and in Π¹₂ for height 3, and (iii) Π¹_n-3- and Σ¹_n-3-hard and in Π¹_2n-4 (assuming CH) for all n > 3. All proofs are elementary and do not rely on theorems from set theory.

Related

• The Isomorphism Problem On Classes of Automatic Structures
• Isomorphism of regular trees and words
• Isomorphisms of scattered automatic linear orders
• Club isomorphisms on higher Aronszajn trees
• The isomorphism problem for tree-automatic ordinals with addition