Automatic Structures and Model Theory
(Abstract)

Khoussainov and Nerode posed various open questions on automatic structures and model theory. Pavel Semukhin and Frank Stephan were able to solve some of these and showed the following: (1) There are automatic structures with exactly n automatic models where n in {3,4,5,...}; these models are then also all automatic models. (2) There are automatic structures where the prime model is automatic and there are countably many further nonautomatic countable models. (3) If LOGSPACE = P then there is a aleph₁-categorical but not aleph₀-categorical theory which has countably many model of which all but the prime model are automatic. (4) There is a theory with countably many countable models including a countable prime model and countable saturated model such that the saturated model but not the prime model is automatic.