Kurt Gödel Research Center

2013 seminar talk: Automatic models of first-order theories

Talk held by Pavel Semukhin (KGRC) at the KGRC seminar on 2013-11-14.

Abstract

An automatic structure is an algebraic structure whose operations and relations can be recognized by finite automata. In the first part of this talk I'll provide a general introduction to automatic structures. The second part will be devoted to our joint work with Frank Stephan on model theoretical properties of automatic structures. We will consider the questions like (1) If a complete theory T has only countably many countable model (in particular, if T is uncountably categorical) and one of the models of T is automatic, are all the other models of T automatic? (2) Fix N>=1; is there a complete theory that has exactly N automatic models? (3) If the countable saturated model of T is automatic, does this imply that the prime model of T is also automatic?