dc.contributor.author Kuske, D dc.contributor.author Liu, J dc.contributor.author Lohrey, M dc.date.accessioned 2011-11-27T02:31:28Z dc.date.available 2011-11-27T02:31:28Z dc.date.copyright 2010 dc.date.issued 2011-11-27 dc.identifier.citation Computer 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.isbn 978-3-642-15204-7 dc.identifier.issn 0302-9743 (Print) 1611-3349 (Online) dc.identifier.uri http://hdl.handle.net/10292/2806 dc.description.abstract The 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.publisher Springer Berlin / Heidelberg dc.relation.uri http://dx.doi.org/10.1007/978-3-642-15205-4_31 dc.rights An 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.title The isomorphism problem for ω-automatic trees dc.type Conference Contribution dc.rights.accessrights OpenAccess dc.identifier.doi 10.1007/978-3-642-15205-4_31
﻿