B. Khoussainov; "Automata and Structures", 21.12.2005, 13:40, G035

Automata and Structures

Bakhadyr Khoussainov
University of Auckland, New Zealand

Abstract:
We introduce the concept of automatic structure. Informally, these are the structures that can be defined in terms of automata Here  by automata we mean any of the following classes of finite state machines  finite automata, tree automata, Buchi automata, Rabin automata.

Nerode and the speaker initiated the systematic study of automatic structures in 94. An important property of automatic structures is that these structures are closed under first order interpretations and have effective semantics. In particular, the first order theory of any automatic structure is decidable.

The theory of automatic structures has become an active area of research in the last decade with several new and exciting results. In this talk we survey  recent results in the area and outline some of the interesting proofs. We also provide many examples of automatic structures.

Some of the results of the talk are published in LICS 01-04 and STACS04 conference proceedings. Results are joint with Nerode, Rubin, Stephan, and Nies.

December 21, 2005, 13:40, G035