Tree-automatic well-founded trees

DOI10.2168/LMCS-9(2:10)2013zbMATH Open1297.03024arXiv1201.5495MaRDI QIDQ5891070FDOQ5891070

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

Publication date: 9 July 2013

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1201.5495

Recommendations

• Tree-automatic well-founded trees
• The rank of tree-automatic linear orderings
• Automatic linear orders and trees
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for \(\omega \)-automatic trees

zbMATH Keywords

isomorphism problemordinal rankhyperarithmetical hierarchywell-founded treestree-automatic structures

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57)

Cited In (9)

• Automatic linear orders and trees
• Model-theoretic complexity of automatic structures
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• The isomorphism problem for \(\omega \)-automatic trees
• The rank of tree-automatic linear orderings
• One-stage tree: end-to-end tree builder and pruner
• Tree-automatic well-founded trees
• The isomorphism problem on classes of automatic structures with transitive relations
• Title not available (Why is that?)

This page was built for publication: Tree-automatic well-founded trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891070)