Automata and Space-Filling Curves

Faculty Member

Philipp Hieronymi and Erik Walsberg

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: let $r \in \mathbb{N}_{>1}$ and let $C \subseteq \mathbb{R}^n$ be a geometrically interesting set (often a fractal), 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, this project aims to determine whether graphs of space-filling curves can be recognized in this way.

Team Meetings

At least biweekly

Project Difficulty


Undergrad Prerequisites

Completion of MATH 347 and 400-level real analysis course are required. Completion of MATH 414 or CS 374 helpful, but knowledge of logic or automata theory is not a prerequisite.