Automatic Structures

Bakhadyr Khoussainov


The theory of automatic structures is a new and attractive area of research in modern theoretical computer science, logic, and computability. In this series of talks, we present a gentle introduction to the theory by covering most of the foundational topics in the area. The first lecture will be introductory in which we motivate the topic, define automatic structures, and present many examples. We provide a foundational theorem proved by Nerode and the speaker that the first order theory of any automatic structure is decidable. In the second lecture we discuss issues related to existence of automatic presentations of structures typical to mathematics, logic and computer science such as linear orders, trees, graphs, Boolean algebras, groups, and Fraisse limits (e.g. random graphs). In the last lecture, we study a foundational topic in logic, - the interplay between computability and definablity in the world of automatic structures. Most of the results in these series of lectures are obtained in collaboration with Nerode (Cornell), Ishihara (JAIST), Nies (Auckland), Rubin (Auckland), Stephan (Heidelberg). Most of the topics and results covered in these lectures will appear in Rubin's PhD thesis.

Things to know and read:

1. Automata:
Elementary introduction to finite automata theory will suffice.
a) Sipser's book or any Stage 2 or Stage 3 mathematical foundations  of computer science book that covers finite automata.
b) For advanced reading (but not necessary for the lectures) see the book by Khoussainov and Nerode.

2. Structures:
Things to know are the very basics of linear orders, trees, groups, graphs, fields. The general definition of
a structure (or equivalently algebraic system, model) is useful to know.
a) Any Stage 2 or 3 reading material on abstract algebra.
a) For advanced reading (but not necessary for the lectures) see the book by Hodges on model theory.

3. Logic:
Elementary introduction to the first order logic.
a) Initial chapters in any book on an introduction to the first order logic will suffice.
b) For advanced reading (but not necessary for the lectures) see the book by Nerode and Shore Logic for Applications, or the book by Hodges mentioned above.