Tree-automatic well-founded trees

Date
2013-06-25
Authors
Liu, J
Kartzow, A
Lohrey, M
Huschenbett, M
Supervisor
Item type
Journal Article
Degree name
Journal Title
Journal ISSN
Volume Title
Publisher
International Federation of Computational Logic
Abstract

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.

Description
Keywords
Source
Logical Methods in Computer Science, vol.9(2), pp.1 - 44 (44)
Rights statement
Logical Methods in Computer Science is a fully refereed, open access, free, electronic journal.Copyright is retained by the author. Full-text access to all papers is freely available.