Tree-Automatic Well-Founded Trees

Huschenbett, Martin; Kartzow, Alexander GND; Liu, Jiamou; Lohrey, Markus GND

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. Moreover, we make a step towards proving that the ranks of tree-automatic well-founded partial orders are bounded by omega^omega^omega: we prove this bound for what we call upwards linear partial orders. As an application of our result, we show that the isomorphism problem for tree-automatic well-founded trees is complete for level Delta^0_{omega^omega} of the hyperarithmetical hierarchy with respect to Turing-reductions.

Cite

Citation style:

Huschenbett, Martin / Kartzow, Alexander / Liu, Jiamou / et al: Tree-Automatic Well-Founded Trees. 2013.

Access Statistic

Total:
Downloads:
Abtractviews:
Last 12 Month:
Downloads:
Abtractviews:

open graphic

Rights

Export