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

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.

Classification : 03D05, 68Q45, 68R15, 54H05
Keywords: Borel set, Borel function, automata, sequential machine

[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). | Zbl | MR

[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. | Zbl | Numdam

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

[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). | Zbl | MR

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

[17] L.H. Landweber, Decision problem for $\omega$-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