Abstract: 

Since Julius Büchi established a connection between automata and structures coming from mathematical logic, there has been a rich exploration of the implications of this correspondence. From the model-theoretic perspective, there is a natural link between the boolean algebra of definable sets and that of automata and the "regular languages" that they recognize. When we take the further step of associating strings in base ten with the numbers that they represent, we are also able to draw connections between geometric phenomena and properties of automata. For example, say that a subset X of the reals is "ten-regular" if there is a Büchi automaton that accepts (one of) the decimal representations of every element of X, and rejects the decimal representations of each element in its complement. Generalizing this, any additive group of numbers is ten-regular if all of its definable sets are ten-regular. Replacing base ten with any finite base (or appropriate numeration system) we can talk about "automatic sets" and automatic structures. In this talk, we will discuss what it means for an automatic structure to have a "tame geometry," and for which automatic structures over the reals do we understand what the possible geometries are.

Zoom:717 463 6082