Show simple item record

dc.contributor.authorKuske, D
dc.contributor.authorLiu, J
dc.contributor.authorLohrey, M
dc.date.accessioned2011-11-27T02:31:28Z
dc.date.available2011-11-27T02:31:28Z
dc.date.copyright2010
dc.date.issued2011-11-27
dc.identifier.citationComputer Science Logic: Proceedings from the 24th International Workshop, CSL 2010, 19th Annual Conference of the EACSL, Brno, Czech Republic, vol.6247, pp. 396 - 410
dc.identifier.isbn978-3-642-15204-7
dc.identifier.issn0302-9743 (Print) 1611-3349 (Online)
dc.identifier.urihttp://hdl.handle.net/10292/2806
dc.description.abstractThe main result of this paper is that the isomorphism problem for ω-automatic trees of finite height is at least as hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies [9] showing that the isomorphism problem for ω-automatic structures is not ∑_2^1. Moreover, assuming the continuum hypothesis CH, we can show that the isomorphism problem for ω-automatic trees of finite height is recursively equivalent with second-order arithmetic. On the way to our main results, we show lower and upper bounds for the isomorphism problem for ω-automatic trees of every finite height: (i) It is decidable (∏_1^0-complete, resp.) for height 1 (2, resp.), (ii) (∏_1^1-hard and in (∏_2^1 for height 3, and (iii) (∏_(n-3)^1- and (∏_(n-3)^1-hard and in (∏_(2n-4)^1(assuming CH) for all n ≥ 4. All proofs are elementary and do not rely on theorems from set theory. Complete proofs can be found in [18].
dc.publisherSpringer Berlin / Heidelberg
dc.relation.urihttp://dx.doi.org/10.1007/978-3-642-15205-4_31
dc.rightsAn author may self-archive an author-created version of his/her article on his/her own website and or in his/her institutional repository. He/she may also deposit this version on his/her funder’s or funder’s designated repository at the funder’s request or as a result of a legal obligation, provided it is not made publicly available until 12 months after official publication. He/ she may not use the publisher's PDF version, which is posted on www.springerlink.com, for the purpose of self-archiving or deposit. Furthermore, the author may only post his/her version provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at www.springerlink.com”. (Please also see Publisher’s Version and Citation)
dc.titleThe isomorphism problem for ω-automatic trees
dc.typeConference Contribution
dc.rights.accessrightsOpenAccess
dc.identifier.doi10.1007/978-3-642-15205-4_31


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record