AUT LibraryAUT
View Item 
  •   Open Research
  • AUT Faculties
  • Faculty of Design and Creative Technologies (Te Ara Auaha)
  • School of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, Pāngarau
  • View Item
  •   Open Research
  • AUT Faculties
  • Faculty of Design and Creative Technologies (Te Ara Auaha)
  • School of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, Pāngarau
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

The isomorphism problem for ω-automatic trees

Kuske, D; Liu, J; Lohrey, M
Thumbnail
View/Open
csl-final.pdf (210.1Kb)
Permanent link
http://hdl.handle.net/10292/2806
Metadata
Show full metadata
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].
Date
2010
Source
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
Item Type
Conference Contribution
Publisher
Springer Berlin / Heidelberg
DOI
10.1007/978-3-642-15205-4_31
Publisher's Version
http://dx.doi.org/10.1007/978-3-642-15205-4_31
Rights Statement
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)

Contact Us
  • Admin

Hosted by Tuwhera, an initiative of the Auckland University of Technology Library

 

 

Browse

Open ResearchTitlesAuthorsDateSchool of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, PāngarauTitlesAuthorsDate

Alternative metrics

 

Statistics

For this itemFor all Open Research

Share

 
Follow @AUT_SC

Contact Us
  • Admin

Hosted by Tuwhera, an initiative of the Auckland University of Technology Library