## Abstract

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

Original language | English (US) |
---|---|

Article number | 17 |

Journal | Logical Methods in Computer Science |

Volume | 16 |

Issue number | 1 |

DOIs | |

State | Published - 2020 |

## Keywords

- Büchi automata
- Differentiabilty
- Fractals
- GDFIS
- PSPACE
- Regular functions
- Regular real analysis

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)