CofC Logo

October 19 Math Colloquium

Doug Cenzer, University of Florida

Complexity of Automatic Structures and Isomorphisms

Sets, relations and functions on finite strings are said to be automatic if they can be computed by finite automata. This is a classic form of online computation.
Structures are automatic if they have an automatic universe and automatic relations and functions.
There are several fundamental problems for a given class of structures, such as orderings, groups, equivalence structures:
1. Characterize the automatic copies of such structures. For example, automatic well-orderings have copies up to the ordinal ωω.
2. The model checking problem: determine whether a given structure satisfies a given sentence. For any automatic structure, this is decidable.
3. The isomorphism problem: determine whether two given structures are isomorphic. In general, this is a Σ11 problem. For automatic well-orderings, this is decidable.
4. The complexity of categoricity problem: computing an isomorphism between two isomorphic structures.
We will present some new results on automatic equivalence structures and isomorphisms between such structures.
There is an automatic copy of the universal countable equivalence structure. Any two isomorphic automatic equivalence structures are computably isomorphic.
For unary structures, this is improved to a linear time isomorphism.

Social Media