Continuous regular functions

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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article number17
JournalLogical Methods in Computer Science
Volume16
Issue number1
DOIs
StatePublished - 2020

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Continuous regular functions'. Together they form a unique fingerprint.

Cite this