Baire and automata

Abstract : In his thesis Baire defined functions of Baire class 1. A function f is of Baire class 1 if it is the pointwise limit of a sequence of continuous functions. Baire proves the following theorem. A function f is not of class 1 if and only if there exists a closed nonempty set F such that the restriction of f to F has no point of continuity. We prove the automaton version of this theorem. An ω-rational function is not of class 1 if and only if there exists a closed nonempty set F recognized by a Büchi automaton such that the restriction of f to F has no point of continuity. This gives us the opportunity for a discussion on Hausdorff's analysis of Δ°2, ordinals, transfinite induction and some applications of computer science.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [97 references]  Display  Hide  Download

https://hal.inria.fr/hal-00966518
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, March 26, 2014 - 5:00:53 PM
Last modification on : Thursday, January 11, 2018 - 6:16:28 AM
Document(s) archivé(s) le : Thursday, June 26, 2014 - 11:57:44 AM

File

676-2388-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00966518, version 1

Citation

Pierre Simonnet, Benoit Cagnard. Baire and automata. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (2), pp.255--295. ⟨hal-00966518⟩

Share

Metrics

Record views

272

Files downloads

430