Résumé
Soit (u(n)) une suite de ±1 engendrée par un 2-automate, nous montrons que la fonction génératrice associée
a des propriétés généralisant celles de la fonction de Thue-Morse:
Il existe un vecteur F(Z) dont une des composantes est f(Z) et une matrice carrée M(Z) tels que l'on ait: F(Z)=M(Z)F(Z2) d'où une expression de F par un produit infini (matriciel). De plus nous donnons des développements en séries de fractions rationnelles pour f. Enfin, dans le cas particulier de la fonction de Thue-Morse, nous montrons que tous les points du cercle unité sont des singularités de type non algébrique.
Preview
Unable to display preview. Download preview PDF.
References
J.P. ALLOUCHE, Théorie des nombres et automates, Thèse, Bordeaux, 1983.
J.P. ALLOUCHE, Automates finis en théorie des nombres, à paraître dans Expo. Math., 1987.
J.M. AUTEBERT, P. FLAJOLET, J. GABARRO, Prefixes of infinite words and ambiguous context-free languages, Inform. Process. Lett. 25, 4, 1987, p. 211–216.
M. BALAZARD, Communication privée.
J. BERSTEL, Every iterated morphism yields a Co-CFL, Inform. Process. Lett. 22, 1, 1986, p. 7–9.
J. BEAUQUIER, L. THIMONIER, Prefix-free words of length n over m letters: two-sided well balanced parentheses and palindroms, Colloque de combinatoire énumérative U.Q.A.M. 1985, Canada, Lect. Notes in Math., 1234, p. 27–33.
G. CHRISTOL, T. KAMAE, M. MENDES FRANCE et G. RAUZY, Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108, 1980, p. 401–419.
L. COMTET, Analyse combinatoire, P.U.F., Paris 1970.
F.M. DEKKING, Transcendance du nombre de Thue-Morse, C.R. Acad. Sci., sér. A, t. 285, 1977, p. 157–160.
P. DUMAS, L. THIMONIER, On generating functions of the language of the prefix-free palindroms over m letters, Rapport L.R.I., 1987.
S. EILENBERG, Automata, languages and machines, vol. A, Academic Press, 1976.
P. FLAJOLET, Analytic models and ambiguity of context-free languages, Theoretical Computer Science 49, 1987, p. 283–309.
P. FLAJOLET and N. MARTIN, Probabilistic counting algorithms and data base applications, J. Computer System Sc., 31, 1985, p. 182–209.
P. FLAJOLET, M. REGNIER, D. SOTTEAU, Algebraic methods for trie statistics, Ann. Discr. Math., 25, 1985, p. 145–188.
P. FLAJOLET, R. SEDGEWICK, Mathematical analysis of algorithms, Cours de l'Université de Princeton, U.S.A., 1986.
J.H. LOXTON and A. J. Van Der POORTEN, Arithmetic properties of the solutions of a class of functional equations, J. Reine Angew. Math., 330, 1982, p. 159–172.
G. POLYA, Collected papers, Vol. 1, Singularities of analytic functions, R.P. Boas ed., the M.I.T. Press, Cambridge, 1974.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Allouche, JP., Rande, B., Thimonier, L. (1988). Fonctions Generatrices Transcendantes a Coefficients Engendres par Automates. In: Cori, R., Wirsing, M. (eds) STACS 88. STACS 1988. Lecture Notes in Computer Science, vol 294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0035843
Download citation
DOI: https://doi.org/10.1007/BFb0035843
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18834-6
Online ISBN: 978-3-540-48190-4
eBook Packages: Springer Book Archive