Definability on the Reals from Büchi Automata

Abstract: Büchi automata are the natural analogue of finite automata in the context of infinite strings (indexed by the natural numbers) on a finite alphabet. We say a subset X of the reals is r-regular if there is a Büchi automaton that accepts (one of) the base-r representations of every element in X, and rejects the base-r representations of each element in its complement. These sets often exhibit fractal-like behavior—e.g., the Cantor set is 3-regular. There are remarkable connections in logic to Büchi automata, particularly in model theory. In this talk, I will give a characterization of when the expansion of the real ordered additive group by a predicate for a closed r-regular subset of [0,1] is model-theoretically tame (d-minimal, NIP, NTP2). Moreover, I will discuss how this coincides with geometric tameness, namely trivial fractal dimension. This will include a discussion of how the properties of definable sets vary depending on the properties of the Büchi automaton that recognizes the predicate subset.

formal languages and automata theorylogicmetric geometry

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic