Show simple item record

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.issued2014-02-13
dc.identifier.citationLogical Methods in Computer Science, vol.9(2), pp.1 - 44 (44)
dc.identifier.urihttp://hdl.handle.net/10292/6736
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.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.titleTree-automatic well-founded trees
dc.typeJournal Article
dc.rights.accessrightsOpenAccess
dc.identifier.doi10.2168/LMCS-9(2:10)2013
aut.relation.articlenumber10
aut.relation.endpage44
aut.relation.issue2
aut.relation.pages44
aut.relation.startpage1
aut.relation.volume9
pubs.elements-id160914


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record