We investigate tree-automatic well-founded trees. For this, we introduce a new ordinal measure for well-founded trees, called ∞-rank. The ∞-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 ω~w. As a corollary, we obtain that the ordinal rank of a string-automatic (resp., tree-automatic) well-founded tree is strictly below ω~2 (resp., ω~W). 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 ω~w. As a second application of the ∞-rank we show that the isomorphism problem for tree-automatic well-founded trees is complete for level △_(ω~w)~0 of the hyperarithmetical hierarchy (under Turing-reductions). Full proofs can be found in the arXiv-version [11] of this paper.
展开▼
