Continuous Regular Functions

Abstract

Following Chaudhuri, Sankaranarayanan, and Vardi, we say that a function $f:[0,1]\to [0,1]$ is $r$-regular if there is a Büchi automaton that accepts precisely the set of base $r\in \mathbb{N}$ representations of elements of the graph of $f$. We show that a continuous $r$-regular function $f$ is locally affine away from a nowhere dense, Lebesgue null, subset of $[0,1]$. As a corollary we establish that every differentiable $r$-regular function is affine. It follows that checking whether an $r$-regular function is differentiable is in $\mathrm{PSPACE}$. Our proofs rely crucially on connections between automata theory and metric geometry developed by Charlier, Leroy, and Rigo.

References in corpus (1)

• Definability and decidability in expansions by generalized Cantor sets

Cited by in corpus (1)

• On the bijective colouring of Cantor trees based on transducers