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

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 .

Publié le : 2006-01-01
DOI : https://doi.org/10.5802/aif.2246
Classification:  68R15,  11B85
Mots clés: mots infinis, complexité, substitutions, automates 
@article{AIF_2006__56_7_2463_0,
     author = {Le Gonidec, Marion},
     title = {Sur la complexit\'e de mots infinis engendr\'es par des $q$-automates d\'enombrables},
     journal = {Annales de l'Institut Fourier},
     volume = {56},
     year = {2006},
     pages = {2463-2491},
     doi = {10.5802/aif.2246},
     zbl = {1121.68090},
     mrnumber = {2290787},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/AIF_2006__56_7_2463_0}
}

Le Gonidec, Marion. Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables. Annales de l'Institut Fourier, Tome 56 (2006) pp. 2463-2491. doi : 10.5802/aif.2246. http://gdmltest.u-ga.fr/item/AIF_2006__56_7_2463_0/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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, Elsevier, Pure and Applied Mathematics, Tome 141 (2004) | Zbl 02206109

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

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

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