| Autor: |
Alexi Block Gorman, Philipp Hieronymi, Elliot Kaplan, Ruoyu Meng, Erik Walsberg, Zihe Wang, Ziqin Xiong, Hongru Yang |
| Jazyk: |
angličtina |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Logical Methods in Computer Science, Vol Volume 16, Issue 1 (2020) |
| Druh dokumentu: |
article |
| ISSN: |
1860-5974 |
| DOI: |
10.23638/LMCS-16(1:17)2020 |
| Popis: |
Following Chaudhuri, Sankaranarayanan, and Vardi, we say that a function $f:[0,1] \to [0,1]$ is $r$-regular if there is a B\"{u}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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
