Huschenbett, Martin and Kartzow, Alexander and Liu, Jiamou and Lohrey, Markus - Tree-Automatic Well-Founded Trees

lmcs:721 - Logical Methods in Computer Science, June 25, 2013, Volume 9, Issue 2
Tree-Automatic Well-Founded Trees

Authors: Huschenbett, Martin and Kartzow, Alexander and Liu, Jiamou and Lohrey, Markus

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.


Source : oai:arXiv.org:1201.5495
DOI : 10.2168/LMCS-9(2:10)2013
Volume: Volume 9, Issue 2
Published on: June 25, 2013
Submitted on: November 1, 2012
Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic


Share

Consultation statistics

This page has been seen 73 times.
This article's PDF has been downloaded 29 times.