Tree-Automatic Well-Founded Trees

Abstract

We investigate tree-automatic well-founded trees. For this, we introduce a new ordinal measure for well-founded trees, called ∞-rank. The ∞-rankof 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 ∞-rankis always finite. Here, using Delhommé’s decomposition technique for tree-automatic structures, we show that the ∞-rankof 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 ω ² (resp., ω ^ω). The result for the string-automatic case nicely contrasts a result of Delhommé, saying that the ranks of string-automatic well-founded partial orders reach all ordinals below ω ^ω. As a second application of the ∞-rankwe show that the isomorphism problem for tree-automatic well-founded trees is complete for level $\Delta^0_{\omega^\omega}$ of the hyperarithmetical hierarchy (under Turing-reductions). Full proofs can be found in the arXiv-version [11] of this paper.