The isomorphism problem on automatic linear orders and trees

Abstract

Automatic structures are finitely presented structures where the universe and all relations can be recognized by finite automata. Such structures form a subclass of computable (or recursive) structures and every automatic structure has a decidable first-order theory\cite{KhoN95,BluG00}. A well-studied problem in the study of algorithmic/recursive model theory is the isomorphism problem, which asks whether two given finitely presented structures (over the same signature) are isomorphic. It is known that the isomorphism problem for automatic structures is complete for the first level of the analytical hierarchy $\Sigma^1_1$\cite{KhoNRS07}. It follows that $\Sigma^1_1$-completeness also holds for the class of automatic successor trees and automatic partial orders\cite{Nies07}. In \cite{KuLiLo10,Liu10}, it is shown that (1) the isomorphism problem for automatic trees of height at most $n\geq 2$ is complete for the level of $\Pi^0_{2n-3}$ of the arithmetic hierarchy, (2) the isomorphism problem for automatic trees of finite height is recursively equivalent to true arithmetic. In this talk, we will discuss two recent results along this line of research: (i) The isomorphism problem for automatic order trees is $\Sigma^1_1$-complete. (ii) The isomorphism problem for automatic linear orders is $\Sigma^1_1$-complete. We will also discuss the isomorphism problem for a class of linear orders presented by context-free languages. The work is joint with Dietrich Kuske and Markus Lohrey.