2009 seminar talk: A survey of automatic structures

Talk held by Pavel Semukhin (National University of Singapore) at the KGRC seminar on 2009-10-08.


Automatic structures are the algebraic structures whose basic relations and functions are recognizable by finite automata. In this survey talk, I will first give main definitions and discuss general properties of automatic structures. In the second part, we will consider the problem of characterizing the automatic structures in some particular classes of models, like linear orders, groups, Boolean algebras, etc. As an example, we will prove non-automaticity of the ordinal ωω and (N,*), the natural numbers with multiplication.

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.