The Isomorphism Problem On Classes of Automatic Structures

2010/01/13 by Kuske, Dietrich, Liu, Jiamou, Lohrey, Markus
#F.4.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1001.2086

Abstract

Automatic structures are finitely presented structures where the universe and all relations can be recognized by finite automata. It is known that the isomorphism problem for automatic structures is complete for Σ¹₁; the first existential level of the analytical hierarchy. Several new results on isomorphism problems for automatic structures are shown in this paper: (i) The isomorphism problem for automatic equivalence relations is complete for Π⁰₁ (first universal level of the arithmetical hierarchy). (ii) The isomorphism problem for automatic trees of height n ≥ 2 is Π⁰_2n-3-complete. (iii) The isomorphism problem for automatic linear orders is not arithmetical. This solves some open questions of Khoussainov, Rubin, and Stephan.

Related

• The Isomorphism Problem for omega-Automatic Trees
• Isomorphisms of scattered automatic linear orders
• Isomorphism of regular trees and words
• Three Lectures on Automatic Structures
• Structures Without Scattered-Automatic Presentation