A Hierarchy of Expressive Power for Automatic Sets of Natural Numbers

There are compelling and long-established connections between automata theory and mathematical logic, including finite automata and the additive monoid of natural numbers. We say a subset X of the natural numbers is “k-automatic” if there is a finite automaton that accepts the base-k representations of every element of X, and rejects the base-k representations of each element in its complement. In this talk, we will discuss the hierarchy of finite automata in terms of their expressive power–what other automata can we build from a few basic ones and (most of) the classic automata operations? We will unpack the connection between this question and tools from first-order logic.