A survey of automatic structures

KGRC Research Seminar | 08.10.2009 15:00 - 16:30

P. Semukhin (National University of Singapore, SG)

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.

Organiser:

KGRC

Location:

SR 101, 2. St., Währinger Str. 25