Alexi Block Gorman, Fields Institute
"Fractal Dimensions and Definability from Büchi Automata"
Büchi automata are the natural extension of finite automata, also called finite-state machines, to a model of computation 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 representations of every element of X, and rejects the base-r representations of each element in its complement. We can analogously define r-regular subsets of higher arities, and these sets often exhibit fractal-like behavior--e.g., the Cantor set is 3-regular. There are compelling connections between fractal geometry, r-regular subsets of the reals, and the directed graph structure of the automata that witness regularity. For an r-regular subset of the unit box in n-dimensional Euclidean space, we will describe how to obtain Hausdorff dimension, Box counting dimension, and Hausdorff measure (for the appropriate dimension) in terms of a certain variation of induced sub-automata. We will also see how this gives us a characterization for when reducts of a relevant first-order structure, one expanding the reals as an ordered additive group, have definable unary sets whose Hausdorff dimension and Boxing counting dimension disagree. This is joint work with Christian Schulz.