×

Continuous regular functions. (English) Zbl 1528.03188

Summary: Following S. Chaudhuri et al. [in: Proceedings of the 2013 28th annual ACM/IEEE symposium on logic in computer science, LICS 2013, Tulane University, New Orleans, LA, USA, June 25–28, 2013. Los Alamitos, CA: IEEE Computer Society. 509–518 (2013; Zbl 1366.03217)], 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 PSPACE. Our proofs rely crucially on connections between automata theory and metric geometry developed by É. Charlier et al. [Adv. Math. 280, 86–120 (2015; Zbl 1332.28013)].

MSC:

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

References:

[1] Boris Adamczewski and Jason Bell. An analogue of Cobham’s theorem for fractals.Trans. Amer. Math. Soc., 363(8):4421-4442, 2011. · Zbl 1229.28007
[2] Vladimir S. Anashin. Quantization causes waves: Smooth finitely computable functions are affine. p-Adic Numbers, Ultrametric Analysis and Applications, 7(3):169-227, 2015. · Zbl 1328.81136
[3] Bernard Boigelot, Louis Bronne, and St´ephane Rassart. An improved reachability analysis method for strongly linear hybrid systems (extended abstract). In Orna Grumberg, editor,Computer Aided
[4] William Balderrama and Philipp Hieronymi. Definability and decidability in expansions by generalized Cantor sets.Preprint arXiv:1701.08426, 2017.
[5] Siddharth Bhaskar. Personal communication. 2018.
[6] Bernard Boigelot, S´ebastien Jodogne, and Pierre Wolper. An effective decision procedure for linear arithmetic over the integers and reals.ACM Trans. Comput. Log., 6(3):614-633, 2005. · Zbl 1407.03052
[7] Bernard Boigelot, St´ephane Rassart, and Pierre Wolper. On the expressiveness of real and integer arithmetic automata (extended abstract). InProceedings of the 25th International Colloquium · Zbl 0910.68149
[8] Emilie Charlier, Julien Leroy, and Michel Rigo. An analogue of Cobham’s theorem for graph´ directed iterated function systems.Adv. Math., 280:86-120, 2015. · Zbl 1332.28013
[9] Swarat Chaudhuri, Sriram Sankaranarayanan, and Moshe Y. Vardi. Regular real analysis. In2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2013), pages 509-518. · Zbl 1366.03217
[10] Antongiulio Fornasiero, Philipp Hieronymi, and Erik Walsberg. How to avoid a compact set.Adv. Math., 317:758-785, 2017. · Zbl 1414.03009
[11] David Hilbert. Ueber die stetige Abbildung einer Line auf ein Fl¨achenst¨uck.Math. Ann., 38(3):459- 460, 1891. · JFM 23.0422.01
[12] John E. Hutchinson. Fractals and self-similarity.Indiana Univ. Math. J., 30(5):713-747, 1981. · Zbl 0598.28011
[13] Philipp Hieronymi and Erik Walsberg. On continuous functions definable in expansions of the ordered real additive group.Preprint, arXiv:1709.03150, 2017. · Zbl 1436.03209
[14] Michal Koneˇcn´y. Real functions computable by finite automata using affine representations.Theoret. Comput. Sci., 284(2):373-396, 2002. Computability and complexity in analysis (Castle Dagstuhl, · Zbl 1039.68050
[15] Jouni Luukkainen. Assouad dimension: antifractal metrization, porous sets, and homogeneous measures.J. Korean Math. Soc., 35(1):23-76, 1998. · Zbl 0893.54029
[16] Jean-Michel Muller. Some characterizations of functions computable in on-line arithmetic.IEEE Trans. Comput., 43(6):752-755, 1994. · Zbl 1042.68503
[17] A. Prasad Sistla, Moshe Y. Vardi, and Pierre Wolper. The complementation problem for B¨uchi automata with applications to temporal logic.Theoret. Comput. Sci., 49(2-3):217-237, 1987. Twelfth international colloquium on automata, languages and programming (Nafplion, 1985). · Zbl 0613.03015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.