Recherche et téléchargement d’archives de revues mathématiques numérisées

  Table des matières de ce fascicule | Article précédent | Article suivant
Cagnard, Benoit; Simonnet, Pierre
Automata, Borel functions and real numbers in Pisot base. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, 41 no. 1 (2007), p. 27-44
Texte intégral djvu | pdf | Analyses MR 2330041 | Zbl pre05238552
Class. Math.: 03D05, 68Q45, 68R15, 54H05
Mots clés: Borel set, Borel function, automata, sequential machine

URL stable:

Voir cet article sur le site de l'éditeur


This note is about functions $ f: A^\omega \rightarrow 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 : \mathbb{ R} \rightarrow \mathbb{R} $ 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.


[1] A. Avizienis, Signed-digit number representation for fast parallel aritmetic. IRE Trans. Electronic Comput. 10 (1961) 389400.
[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) 111.
[3] C. Choffrut, H. Pelibossian and P. Simonnet, Decision issues on functions realized by finite automata. J. Automata Languages Combin. 4 (1999) 171182.  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) 895897.
[7] O. Finkel, On the topological complexity of infinitary rational relations. Theor. Inform. Appl. 37 (2003) 105113.
Numdam |  Zbl 1112.03313
[8] O. Finkel, Undecidability of topological and arithmetical properties of infinitary rational relations. Theor. Inform. Appl. 37 (2003) 115126.
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 systems, in Ergodic Theory of $Z^d$-Actions. New Brunswick, New Jersey (1996) 345368.  Zbl 0856.11007
[12] C. Frougny, On-the-fly algorithms and sequential machines. IEEE Trans. Comput. 49 (2000) 859863.
[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) 135140.  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) 622629.
[17] L.H. Landweber, Decision problem for $\omega $-automata. Math. Systems. Theory 3 (1969) 376384.  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) 160.  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) 7182.  Zbl 0952.68076
[22] C. Prieur, How to decide continuity of rationnal functions on infinite words (Errata). Theoret. Comput. Sci. 276 (2002) 445447.  Zbl 1052.68080
[23] J. Saint Raymond, Fonctions boréliennes sur un quotient. Bull. Soc. Math. France 100 (1976) 141147.  Zbl 0336.54015
[24] J. Sakarovitch, Éléments de théorie des automates. Vuibert informatique (2003).
[25] W. Sierpinski, Sur les fonctions de première classe. C. R. Acad. Sci. Paris 170 (1920) 919922.  JFM 47.0236.02
Copyright Cellule MathDoc 2014 | Crédit | Plan du site