Kurt Gödel Research Center

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.

Abstract

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.