کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661946 | 1633479 | 2013 | 19 صفحه PDF | دانلود رایگان |
The main result of this paper states that the isomorphism problem for ω-automatic trees of finite height is at least has hard as second-order arithmetic and therefore not analytical. This strengthens a recent result by Hjorth, Khoussainov, Montalbán, and Nies (2008) [12] showing that the isomorphism problem for ω-automatic structures is not in . 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 (-complete, resp.), for height 1 (2, resp.), (ii) -hard and in for height 3, and (iii) - and -hard and in (assuming CH) for height n⩾4. All proofs are elementary and do not rely on theorems from set theory.
Journal: Annals of Pure and Applied Logic - Volume 164, Issue 1, January 2013, Pages 30-48