logo ANNALES DE L'INSTITUT FOURIER

Avec cedram.org

Table des matières de ce fascicule | Article précédent | Article suivant
Marion Le Gonidec
Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables
(Complexity of infinite words generated by countable $q$-automata)
Annales de l'institut Fourier, 56 no. 7 (2006), p. 2463-2491, doi: 10.5802/aif.2246
Article PDF | Analyses MR 2290787 | Zbl 1121.68090 | 3 citations dans Cedram
Class. Math.: 68R15, 11B85
Mots clés: mots infinis, complexité, substitutions, automates

Résumé - Abstract

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 (\log n)^p$.

Bibliographie

[1] J.-P. Allouche, “Sur la complexité des suites infinies”, Bull. Belg. Math. Soc. Simon Stevin 1 (1994) no. 2, p. 133-143 Article |  MR 1318964 |  Zbl 0803.68094
[2] J.-P. Allouche & J. Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge University Press, Cambridge, 2003  MR 1997038 |  Zbl 01993704
[3] J. Berstel & D. Perrin, Theory of codes, Academic Press, 1985  MR 797069 |  Zbl 0587.68066
[4] S. Brlek, “Enumeration of factors in the Thue-Morse word”, Discrete Applied Math. 24 (1989), p. 83-96 Article |  MR 1011264 |  Zbl 0683.20045
[5] A. Cobham, “Uniform-tag sequences”, Math. Syst. Th. 6 (1972), p. 164-192 Article |  MR 457011 |  Zbl 0253.02029
[6] A. Ehrenfeucht, K. P. Lee & G Rozenberg, “Subword complexities of various classes of deterministic developmeltal languages without interactions”, Math. Syst. Theoret. Comput. Science 63 (1975), p.  59-75  MR 388861 |  Zbl 0316.68043
[7] S. Eilenberg, Automata, languages and machines A, Academic Press, 1974  Zbl 0317.94045
[8] S. Ferenczi, “Substitution dynamical systems on infinite alphabets”, to appear in Ann. Inst. Fourier, 2006 Cedram
[9] M. Lothaire, Combinatorics on words, Encyclopedia of Mathematics and Its applications 17, Cambridge University Press, 1983  MR 675953 |  Zbl 0874.20040
[10] M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and Its applications 90, Cambridge University Press, 2002  MR 1905123 |  Zbl 1001.68093
[11] C. Mauduit, “Propriétés arithmétiques des substitutions et automates infinis”, to appear in Ann. Inst. Fourier, 2006 Cedram |  MR 1476736
[12] C. Mauduit & A. Sárközy, “On the arithmetic structure of the integers whose sum of digits is fixed”, Acta Arithmetica LXXXI (1997) no. 2, p.  145-173 Article |  MR 1456239 |  Zbl 0887.11008
[13] B. Mossé, “Reconnaissabilité des substitutions et complexité des suites automatiques”, Bull. Soc. Math. France 124 (1996) no. 2, p.  329-346 Numdam |  MR 1414542 |  Zbl 0855.68072
[14] J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, Automata, languages and programming (Antwerp, 1984), Lecture Notes in Comput. Sci. 172, Springer, 1984, p.  380–389  MR 784265 |  Zbl 0554.68053
[15] D. Perrin & J.-E. Pin, Mots infinis. Technical report 93.40, Laboratoire Informatique Théorique et Programmation. Institut Blaise Pascal, 1997
[16] D. Perrin & J.-E. Pin, Infinite words, Automata, Semigroups, Logic and Games, Pure and Applied Mathematics 141, Elsevier, 2004  Zbl 02206109
[17] N. Pytheas Fogg, 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 1970385 |  Zbl 1014.11015
[18] M. Queffélec, Substitution dynamical systems-spectral analysis, Lecture Notes in Mathematics 1294, Springer-Verlag, Berlin, 1987  MR 924156 |  Zbl 0642.28013
[19] G. Rozenberg & A. Salomaa (Eds), Handbook of formal language, Springer-Verlag, 1997  Zbl 0866.68057
haut