McMaster-Waterloo Model Theory Seminar

Chris Schulz, University of Waterloo

Toward a characterization of k-automatic structures

We consider structures over Presburger arithmetic that include k-automatic sets, that is to say, sets recognized by a base-k finite automaton. The question of how many such structures exist up to interdefinability is a complex one, with a deceptively simple conjectured answer. We give a proof of this conjecture in the restricted case of expansion by a single unary set, and we discuss potential strategies for handling the multivariate case. This talk is based on joint work with Jason Bell and Alexi Block Gorman.

MC 5403