Automata, Borel functions and real numbers in Pisot base
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 1, pp. 27-44.

This note is about functions f:A ω B ω whose graph is recognized by a Büchi finite automaton on the product alphabet A×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: is Baire class 1 if and only if both the overgraph and the undergraph of f are F σ . 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 ω . 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.

DOI : 10.1051/ita:2007007
Classification : 03D05, 68Q45, 68R15, 54H05
Mots clés : Borel set, Borel function, automata, sequential machine
@article{ITA_2007__41_1_27_0,
     author = {Cagnard, Benoit and Simonnet, Pierre},
     title = {Automata, {Borel} functions and real numbers in {Pisot} base},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {27--44},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {1},
     year = {2007},
     doi = {10.1051/ita:2007007},
     mrnumber = {2330041},
     zbl = {1156.03036},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007007/}
}
TY  - JOUR
AU  - Cagnard, Benoit
AU  - Simonnet, Pierre
TI  - Automata, Borel functions and real numbers in Pisot base
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 27
EP  - 44
VL  - 41
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007007/
DO  - 10.1051/ita:2007007
LA  - en
ID  - ITA_2007__41_1_27_0
ER  - 
%0 Journal Article
%A Cagnard, Benoit
%A Simonnet, Pierre
%T Automata, Borel functions and real numbers in Pisot base
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 27-44
%V 41
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007007/
%R 10.1051/ita:2007007
%G en
%F ITA_2007__41_1_27_0
Cagnard, Benoit; Simonnet, Pierre. Automata, Borel functions and real numbers in Pisot base. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 1, pp. 27-44. doi : 10.1051/ita:2007007. http://www.numdam.org/articles/10.1051/ita:2007007/

[1] A. Avizienis, Signed-digit number representation for fast parallel aritmetic. IRE Trans. Electronic Comput. 10 (1961) 389-400.

[2] J.R. Büchi, On a decision method in restricted second order arithmetic, in Methodology and Philosophy of Science. Stanford Univ. Press, Calif. (1962) 1-11.

[3] C. Choffrut, H. Pelibossian and P. Simonnet, Decision issues on functions realized by finite automata. J. Automata Languages Combin. 4 (1999) 171-182. | Zbl

[4] A. Edgar, Classics On Fractals. Studies in non linearity. Westview Press (2004). | Zbl

[5] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York London (1974). | MR | Zbl

[6] M.D. Ercegovac and T. Lang, On-the-fly convertion of redundant into conventional representations. IEEE Trans. Comput. 36 (1987) 895-897.

[7] O. Finkel, On the topological complexity of infinitary rational relations. Theor. Inform. Appl. 37 (2003) 105-113. | Numdam | Zbl

[8] O. Finkel, Undecidability of topological and arithmetical properties of infinitary rational relations. Theor. Inform. Appl. 37 (2003) 115-126. | Numdam | Zbl

[9] G. Flory, Topologie, Analyse. Vuibert (1976).

[10] C. Frougny and J . Sakarovitch, Synchronized relations of finite and infinite words. Theoret. Comput. Sci. (1993) 45-82. | Zbl

[11] C. Frougny and B. Solomyak, On representation of integers in linear numeration systems1996) 345-368. | Zbl

[12] C. Frougny, On-the-fly algorithms and sequential machines. IEEE Trans. Comput. 49 (2000) 859-863.

[13] C. Frougny, Numeration Systems. Chapter 7 of M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press (2002).

[14] F. Gire, Two decidability problems for infinite words. Inform. Proc. Lett. 22 (1986) 135-140. | Zbl

[15] A.S. Kechris, Classical Descriptive Set Theory. Springer-Verlag (1995). | MR | Zbl

[16] P. Kornerup, Digit-set convertions: Generalizations and applications. IEEE Trans. Comput. 43 (1994) 622-629.

[17] L.H. Landweber, Decision problem for ω-automata. Math. Systems. Theory 3 (1969) 376-384. | Zbl

[18] B. Maurey and J.P. Tacchi, Ludwig Scheeffer et les extensions du Théorème des Accroissements Finis, in Séminaire du Luxembourg, Travaux mathématiques, fascicule XIII (2002) 1-60. | Zbl

[19] J.M. Muller, Arithmétique des ordinateurs. Masson, Paris (1989).

[20] D. Perrin and J.-E. Pin, Infinite words, Automata, Semigroups, Logic and Games. Pure Appl. Mathematics Series 141, Academic Press, Elsevier (2004). | Zbl

[21] C. Prieur, How to decide continuity of rationnal functions on infinite words. Theoret. Comput. Sci. 250 (2001) 71-82. | Zbl

[22] C. Prieur, How to decide continuity of rationnal functions on infinite words (Errata). Theoret. Comput. Sci. 276 (2002) 445-447. | Zbl

[23] J. Saint Raymond, Fonctions boréliennes sur un quotient. Bull. Soc. Math. France 100 (1976) 141-147. | Zbl

[24] J. Sakarovitch, Éléments de théorie des automates. Vuibert informatique (2003). | Zbl

[25] W. Sierpinski, Sur les fonctions de première classe. C. R. Acad. Sci. Paris 170 (1920) 919-922. | JFM

Cité par Sources :