Baire and automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2007

Baire and automata

Résumé

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.
Fichier principal
Vignette du fichier
676-2388-1-PB.pdf (435.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00966518 , version 1 (26-03-2014)

Identifiants

Citer

Pierre Simonnet, Benoit Cagnard. Baire and automata. Discrete Mathematics and Theoretical Computer Science, 2007, Vol. 9 no. 2 (2), pp.255--295. ⟨10.46298/dmtcs.392⟩. ⟨hal-00966518⟩
184 Consultations
1115 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More