Automata, Borel functions and real numbers in Pisot base

Cagnard, Benoit ; Simonnet, Pierre

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 1, pp. 27-44.

Résumé

This note is about functions $f:A^{\omega }\to B^{\omega }$ whose graph is recognized by a Büchi finite automaton on the product alphabet $A\times B$. These functions are Baire class 2 in the Baire hierarchy of Borel functions and it is decidable whether such function are continuous or not. In 1920 W. Sierpinski showed that a function $f:ℝ\to ℝ$ is Baire class 1 if and only if both the overgraph and the undergraph of $f$ are $F_{\sigma }$. We show that such characterization is also true for functions on infinite words if we replace the real ordering by the lexicographical ordering on $B^{\omega }$. From this we deduce that it is decidable whether such function are of Baire class 1 or not. We extend this result to real functions definable by automata in Pisot base.

Détail

DOI : 10.1051/ita:2007007

Classification : 03D05, 68Q45, 68R15, 54H05
Mots-clés : Borel set, Borel function, automata, sequential machine