Automata and Differentiable Functions

Faculty Member

Philipp Hieronymi and Erik Walsberg

Project Image


In the last few years novel connections between mathematical logic, automata theory and metric geometry have emerged. A question that often arises in this area is the following: if rise a natural number greater than one, and C is a geometrically interesting subset of Rn, can the set of all r-ary representations of elements of C be recognized by a Büchi automaton? For example, let C be the usual middle-thirds Cantor set. Elements of C are precisely those real numbers in [0,1] that have a ternary representation in which the digit 1 does not occur. Therefore it is not hard to see that the set of ternary representations of elements of C can be recognized by such an automaton. The goal of this project to answer similar questions in the case that C is the graph of a function. In particular, we want know whether there is a non-affine, differentiable function whose graph can be recognized in this way. This is a continuation of the project "Automata and space-filling curves" from the Fall semester 2017.


Team Meetings

At least biweekly

Project Difficulty


Undergrad Prerequisites


Basic knowledge of automata required, and participants should have completed a proof-based course in real analysis.