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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (2), pp.255--295
Liste complète des métadonnées

Littérature citée [97 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00966518
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 17:00:53
Dernière modification le : jeudi 11 janvier 2018 - 06:16:28
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:57:44

Fichier

676-2388-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966518, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

262

Téléchargements de fichiers

368