Bakh Khoussainov

Title: Proving non-automaticity

Abstract:

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.