Logic Seminar
Alexi Block Gorman
UIUC
Fractal Dimensions and Definability from Büchi Automata
Abstract: Büchi automata are the natural extension of finite automata, also called finite-state machines, to a "machine" that accepts infinite-length inputs. 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 expansions of every element in X, and rejects the base-r expansion of each element in its complement. We can analogously define r-regular subsets of higher arities of the reals, and these sets often exhibit fractal-like behavior--e.g., the Cantor set is 3-regular. There are several known--and remarkable--connections in logic to Büchi automata, including the fact that the expansion of the real additive group by every r-regular subset of [0,1] for some fixed positive integer r interprets the monadic second-order theory of the natural numbers with successor. In this talk, I will focus on some of the geometric behavior of closed r-regular set in terms of fractal dimensions, and discuss how closed r-regular sets with and without integer Hausdorff dimension form a dichotomy in terms of first order definability in expansions of the real additive group by a predicate for a specific r-regular set.
Tuesday March 16, 2021 at 4:00 PM in Zoom