Automatic Structures
Bakhadyr Khoussainov
Abstract: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.
Reading:
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.
Reading:
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.
Reading:
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.