The isomorphism problem on automatic linear orders and trees
Date
Authors
Supervisor
Item type
Degree name
Journal Title
Journal ISSN
Volume Title
Publisher
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