Tree-automatic well-founded trees

Simple item page
aut.relation.articlenumber10
aut.relation.endpage44
aut.relation.issue2
aut.relation.pages44
aut.relation.startpage1
aut.relation.volume9
aut.researcherLiu, Jiamou
dc.contributor.authorLiu, J
dc.contributor.authorKartzow, A
dc.contributor.authorLohrey, M
dc.contributor.authorHuschenbett, M
dc.contributor.editorScott, D
dc.contributor.editorAdámek, J
dc.contributor.editorMilius, S
dc.date.accessioned2014-02-12T20:46:03Z
dc.date.available2014-02-12T20:46:03Z
dc.date.copyright2013-06-25
dc.date.issued2013-06-25
dc.description.abstractWe 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.
dc.identifier.citationLogical Methods in Computer Science, vol.9(2), pp.1 - 44 (44)
dc.identifier.doi10.2168/LMCS-9(2:10)2013
dc.identifier.urihttps://hdl.handle.net/10292/6736
dc.languageEnglish
dc.publisherInternational Federation of Computational Logic
dc.relation.urihttp://dx.doi.org/10.2168/LMCS-9(2:10)2013
dc.rightsLogical 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.
dc.rights.accessrightsOpenAccess
dc.titleTree-automatic well-founded trees
dc.typeJournal Article
pubs.elements-id160914
pubs.organisational-data/AUT
pubs.organisational-data/AUT/Design & Creative Technologies
pubs.organisational-data/AUT/Design & Creative Technologies/School of Computing & Mathematical Science
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
A9RF86D.pdf
Size:
487.92 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
licence.htm
Size:
30.34 KB
Format:
Unknown data format
Description:
Download
Collections
School of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, Pāngarau