Automatic Structures and The Isomorphism Problem
Dr Jiamou Liu (Auckland University of Technology)
LOGIC AND COMPUTATION SEMINARDATE: 2012-01-30
TIME: 14:00:00 - 15:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
The study of automatic structures was initiated by Khoussainov and Nerode in 1995 and the field received increasing interests in recent years. Roughly speaking, a relational structure is automatic if its domain and atomic relations can be recognized by synchronous automata. One important property of automatic structures is the decidability of their first-order theories. The first part of the talk will present a gentle introduction to the theory of automatic structures. The second part of the talk will focus on the isomorphism problem. The isomorphism problem is a well-studied problem which asks whether two given structures are isomorphic. I am going to present several results on the isomorphism problem for classes of automatic structures. In particular:
-The isomorphism problem for automatic equivalence structures is Pi^0_1-complete
- The isomorphism problem for automatic linear orders is Sigma^1_1-complete
- The isomorphism problem for automatic order trees is Sigma^1_1-complete
These results answered some major open questions in this field posed by Khoussainov and Nerode.
BIO:
