Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables

Le Gonidec, Marion

Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2463-2491.

On étudie, dans cet article, les propriétés combinatoires de mots engendrés à l’aide de $q$-automates déterministes dénombrables de degré borné, ou de manière équivalente, engendrés par des substitutions de longueur constante uniformément bornées sur un alphabet dénombrable. En particulier, on montre que la complexité de tels mots est au plus polynomiale et que, sur plusieurs exemples, elle est au plus de l’ordre de grandeur de $n{(logn)}^p$.

This article deals with combinatorial properties of infinite words generated by countable and deterministic $q$-automata of bounded degree. Those words can also be viewed as projections of fixed point of some substitutions of constant length on countable alphabet. We show that complexity function of such words is at most polynomial and, on some examples, the order of growth of this function is at most $n{(logn)}^p$.

Classification : 68R15, 11B85
Mot clés : mots infinis, complexité, substitutions, automates
Keywords: Infinite words, complexity, substitutions, automata

[1] Allouche, J.-P. Sur la complexité des suites infinies, Bull. Belg. Math. Soc. Simon Stevin, Volume 1 (1994) no. 2, pp. 133-143 | EuDML | MR | Zbl

[2] Allouche, J.-P.; Shallit, J. Automatic sequences. Theory, applications, generalizations, Cambridge University Press, Cambridge, 2003 | MR | Zbl

[3] Berstel, J.; Perrin, D. Theory of codes, Academic Press, 1985 | MR | Zbl

[4] Brlek, S. Enumeration of factors in the Thue-Morse word, Discrete Applied Math., Volume 24 (1989), pp. 83-96 | DOI | MR | Zbl

[5] Cobham, A. Uniform-tag sequences, Math. Syst. Th., Volume 6 (1972), pp. 164-192 | DOI | MR | Zbl

[6] Ehrenfeucht, A.; Lee, K. P.; Rozenberg, G Subword complexities of various classes of deterministic developmeltal languages without interactions, Math. Syst. Theoret. Comput. Science, Volume 63 (1975), pp.  59-75 | MR | Zbl

[7] Eilenberg, S. Automata, languages and machines, A, Academic Press, 1974 | Zbl

[8] Ferenczi, S. Substitution dynamical systems on infinite alphabets (2006) (to appear in Ann. Inst. Fourier) | EuDML | Numdam | MR | Zbl

[9] Lothaire, M. Combinatorics on words, Encyclopedia of Mathematics and Its applications, 17, Cambridge University Press, 1983 | MR | Zbl

[10] Lothaire, M. Algebraic combinatorics on words, Encyclopedia of Mathematics and Its applications, 90, Cambridge University Press, 2002 | MR | Zbl

[11] Mauduit, C. Propriétés arithmétiques des substitutions et automates infinis (2006) (to appear in Ann. Inst. Fourier) | Numdam | MR

[12] Mauduit, C.; Sárközy, A. On the arithmetic structure of the integers whose sum of digits is fixed, Acta Arithmetica, Volume LXXXI (1997) no. 2, pp.  145-173 | MR | Zbl

[13] Mossé, B. Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, Volume 124 (1996) no. 2, pp.  329-346 | Numdam | MR | Zbl

[14] Pansiot, J.-J. Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming (Antwerp, 1984) (Lecture Notes in Comput. Sci.), Volume 172, Springer, Berlin, 1984, pp.  380-389 | MR | Zbl

[15] Perrin, D.; Pin, J.-E. Mots infinis. Technical report 93.40, Laboratoire Informatique Théorique et Programmation. Institut Blaise Pascal, 1997

[16] Perrin, D.; Pin, J.-E. Infinite words, Automata, Semigroups, Logic and Games, Pure and Applied Mathematics, 141, Elsevier, 2004 | Zbl

[17] Pytheas Fogg, N. Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, 1794, Springer-Verlag, Berlin, 2002 (Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel) | MR | Zbl

[18] Queffélec, M. Substitution dynamical systems-spectral analysis, Lecture Notes in Mathematics, 1294, Springer-Verlag, Berlin, 1987 | MR | Zbl

[19] Rozenberg, G.; Salomaa (Eds), A. Handbook of formal language, Springer-Verlag, 1997 | Zbl