Title: Proving non-automaticity
A structure is (word, tree, omega) automatic if it is isomorphic to a structure whose
domain and relations are recognized by (word, tree, omega) automata in a precise
sense. Examples of automatic structures include the Presburger arithmetic, the term
algebras, configurations spaces of Turing machines, reals with the addition operation.
A foundational question is concerned with finding characterization results for (classes of)
automatic structures. This question is intimately related to discovering new techniques
and ideas for proving or disproving that given structures are automatic. The talk will
outline several techniques of proving non-automaticity of known structures such as
ordinals, Boolean algebras, groups (in particular the additive group of rational numbers),
and the random structures in the case when the underlying automata are finite word automata.