Open problems in the theory of automatic structures

11^th July 2019, 16:00 GHOLT-H223
Prof. Bakh Khoussainov
University of Auckland
Department of Computer Science

Abstract

Automatic structures are algebraic structures, such as graphs, groups
and partial orders, that can be presented by automata. By varying the
classes of automata (e.g. finite automata, tree automata, omega-automata)
one varies the classes of automatic structures. The class of all automatic
structures is robust in the sense that it is closed under many natural algebraic
and model-theoretic operations. In this talk, we give formal definitions to
automatic structures, motivate the study, present many examples, and explain
several fundamental theorems. Some results in the area are deeply connected
with algebra, additive combinatorics, set theory, and complexity theory.
We then motivate and pose several important unsolved questions in the area.

This lecture is given as part of the Aitken Lecture Tour 2019 (https://www.lms.ac.uk/events/lectures/forder-and-aitken-lectureship).