Gorman, Alexi Block and Hieronymi, Philipp and Kaplan, Elliot and Meng, Ruoyu and Walsberg, Erik et al. - Continuous Regular Functions

lmcs:5301 - Logical Methods in Computer Science, February 14, 2020, Volume 16, Issue 1 - https://doi.org/10.23638/LMCS-16(1:17)2020
Continuous Regular Functions

Authors: Gorman, Alexi Block and Hieronymi, Philipp and Kaplan, Elliot and Meng, Ruoyu and Walsberg, Erik and Wang, Zihe and Xiong, Ziqin and Yang, Hongru

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 $\operatorname{PSPACE}$. Our proofs rely crucially on connections between automata theory and metric geometry developed by Charlier, Leroy, and Rigo.

Volume: Volume 16, Issue 1
Published on: February 14, 2020
Submitted on: March 21, 2019
Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic