Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Joint Math Department and CSE Department Theory Seminar

Bakhadyr Khoussainov

Department of Computer Science \\ University of Auckland

Automatic structures

Abstract:

We introduce the concept of automatic structure. Informally, these are structures that can be defined in terms of automata. By automata we mean any of the following machines: finite automata, tree automata, Buchi automata, and 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 the 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 research area in the last decade with new and exciting results. In this talk we survey recent results in the area and outline some of the interesting proofs. The talk will provide many examples. 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.

January 10, 2007

2:00 PM

EBU3b Room 4109

****************************