Expansions of R and N by k-automatic sets: Choose-your-own-adventure!

06.03.2024 11:30 - 13:00

A. Block Gorman (Ohio State University, Columbus, US )


There are compelling and long-established connections between automata theory and model theory, particularly regarding expansions of Presburger arithmetic by sets whose base-\(k\) representations are recognized by a finite-state automaton. We call such sets \(k\)-automatic. Büchi automata are the natural extension of finite-state automata to a model of computation that accepts infinite-length inputs. We say a subset \(X\) of the reals is \(k\)-regular if there is a Büchi automaton that accepts (one of) the base-\(k\) representations of every element of \(X\), and rejects the base-\(k\) representations of each element in its complement. These sets often exhibit fractal-like behavior e.g., the Cantor set is 3-regular.

In this talk we will consider the expansions of Presburger arithmetic and the real additive group by \(k\)-automatic and \(k\)-regular sets respectively. In the real setting, we will discuss dividing lines in definability from the perspectives of both tame geometry and neostability. In the setting of Presburger arithmetic, we obtain a characterization of expansions of \((\mathbb{N},+)\) by unary \(k\)-automatic sets, and discuss its consquences for the decidability and neostability-related properties of related structures.




SR 10, 1. Stock, Koling. 14-16, 1090 Wien