Continuous Regular Functions

MaRDI QIDQ6312303arXivFDO

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

Publication date 10 January 2019

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Computation over the reals, computable analysis (03D78) Lipschitz (Hölder) classes (26A16)

Abstract: Following Chaudhuri, Sankaranarayanan, and Vardi, we say that a function $f:[0,1]o[0,1]$ is $r$-regular if there is a B"{u}chi automaton that accepts precisely the set of base $rinmathbbN$ 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 $operatornamePSPACE$. Our proofs rely crucially on connections between automata theory and metric geometry developed by Charlier, Leroy, and Rigo.

This page was built for publication: Continuous Regular Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312303)