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), p. 27-44 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2007-01-01
DOI : https://doi.org/10.1051/ita:2007007
Classification:  03D05,  68Q45,  68R15,  54H05 
@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},
     volume = {41},
     year = {2007},
     pages = {27-44},
     doi = {10.1051/ita:2007007},
     mrnumber = {2330041},
     zbl = {pre05238552},
     zbl = {1156.03036},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 27-44. doi : 10.1051/ita:2007007. http://gdmltest.u-ga.fr/item/ITA_2007__41_1_27_0/

[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 0943.68106

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

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

[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 1112.03313

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

[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 0783.68065

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

[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 0587.68072

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

[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 0182.02402

[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 1101.01009

[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 1094.68052

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

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

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

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

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