Alexi Block Gorman ; Philipp Hieronymi ; Elliot Kaplan ; Ruoyu Meng ; Erik Walsberg 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: Alexi Block Gorman ; Philipp Hieronymi ; Elliot Kaplan ; Ruoyu Meng ; Erik Walsberg ; Zihe Wang ; Ziqin Xiong ; Hongru Yang

    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
    Accepted on: February 14, 2020
    Submitted on: March 21, 2019
    Keywords: Computer Science - Logic in Computer Science,Mathematics - Logic

    Linked data

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.1901.03366
    • 10.48550/arxiv.1901.03366
    Continuous Regular Functions
    Gorman, Alexi Block ; Hieronymi, Philipp ; Kaplan, Elliot ; Meng, Ruoyu ; Walsberg, Erik ; Wang, Zihe ; Xiong, Ziqin ; Yang, Hongru ;

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 423 times.
    This article's PDF has been downloaded 184 times.