The Isomorphism Problem on Classes of Automatic Structures
Dietrich Kuske, Jiamou Liu, Markus Lohrey · 2010
Several new undecidability results on isomorphism problems for automatic structures are shown: (i) The isomorphism problem for automatic equivalence relations is Π10-complete, (ii) The isomorphism problem for automatic trees of height n ≥ 2 is Π2n-30-complete, (iii) The isomorphism problem for automatic linear orders is not arithmetical.