Tree-Automatic Weil-Founded Trees

摘要

We investigate tree-automatic well-founded trees. For this, we introduce a new ordinal measure for well-founded trees, called oo-rank. The oo-rank of a well-founded tree is always bounded from above by the ordinary (ordinal) rank of a tree. We also show that the ordinal rank of a well-founded tree of ∞-rank α is smaller than ω • (α + 1). For string-automatic well-founded trees, it follows from [16] that the ∞-rank is always finite. Here, using Delhomme's decomposition technique for tree-automatic structures, we show that the ∞-rank of a tree-automatic well-founded tree is strictly below ω~ω. As a corollary, we obtain that the ordinal rank of a string-automatic (resp., tree-automatic) well-founded tree is strictly below ω~2 (resp., ω~ω). The result for the string-automatic case nicely contrasts a result of Delhomme, saying that the ranks of string-automatic well-founded partial orders reach all ordinals below ω~ω, As a second application of the ∞-rank we show that the isomorphism problem for tree-automatic well-founded trees is complete for level △_ω~ω~0 of the hyperarithmetical hierarchy (under Turing-reductions). Full proofs can be found in the arXiv-version [11] of this paper.