Show simple item record

dc.contributor.authorLiu, J
dc.date.accessioned2011-11-27T05:40:20Z
dc.date.accessioned2011-11-28T03:25:15Z
dc.date.accessioned2011-11-28T03:25:49Z
dc.date.available2011-11-27T05:40:20Z
dc.date.available2011-11-28T03:25:15Z
dc.date.available2011-11-28T03:25:49Z
dc.date.copyright2011-07-11
dc.date.issued2011-11-27
dc.identifier.citationLogic Colloquium 2011 ASL European Summer Meeting, Barcelona, Spain, 2011-07-11 - 2011-07-16, pages 76 - 77
dc.identifier.urihttp://hdl.handle.net/10292/2833
dc.description.abstractAutomatic 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.
dc.publisherAssociation of Symbolic Logic
dc.relation.replaceshttp://hdl.handle.net/10292/2818
dc.relation.replaces10292/2818
dc.relation.replaceshttp://hdl.handle.net/10292/2832
dc.relation.replaces10292/2832
dc.relation.urihttp://logic2011.org/?cmd=schedule
dc.rightsAuckland 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.
dc.titleThe isomorphism problem on automatic linear orders and trees
dc.typeConference Contribution
dc.rights.accessrightsOpenAccess


Files in this item

Thumbnail
Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record