The isomorphism problem on automatic linear orders and trees
Date
Authors
Supervisor
Item type
Conference Contribution
Degree name
Journal Title
Journal ISSN
Volume Title
Publisher
Association of Symbolic Logic
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.Description
Keywords
Source
Logic Colloquium 2011 ASL European Summer Meeting, Barcelona, Spain, 2011-07-11 - 2011-07-16, pages 76 - 77
DOI
Publisher's version
Rights statement
Auckland University of Technology (AUT) encourages public access to AUT information and supports the legal use of copyright material in accordance with the Copyright Act 1994 (the Act) and the Privacy Act 1993. Unless otherwise stated, copyright material contained on this site may be in the intellectual property of AUT, a member of staff or third parties. Any commercial exploitation of this material is expressly prohibited without the written permission of the owner.