Sur la complexité de mots infinis engendrés par des q-automates dénombrables
Le Gonidec, Marion1
1 IML Campus de Luminy, case 907 13288 Marseille Cedex 09 (France)
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.

DOI : 10.5802/aif.2246
Classification : 68R15, 11B85
Mot clés : mots infinis, complexité, substitutions, automates
Keywords: Infinite words, complexity, substitutions, automata
Le Gonidec, Marion 1

1 IML Campus de Luminy, case 907 13288 Marseille Cedex 09 (France) 
@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},
     pages = {2463--2491},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     doi = {10.5802/aif.2246},
     zbl = {1121.68090},
     mrnumber = {2290787},
     language = {fr},
     url = {https://www.numdam.org/articles/10.5802/aif.2246/}
}
TY  - JOUR
AU  - Le Gonidec, Marion
TI  - Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables
JO  - Annales de l'Institut Fourier
PY  - 2006
SP  - 2463
EP  - 2491
VL  - 56
IS  - 7
PB  - Association des Annales de l’institut Fourier
UR  - https://www.numdam.org/articles/10.5802/aif.2246/
DO  - 10.5802/aif.2246
LA  - fr
ID  - AIF_2006__56_7_2463_0
ER  - 
%0 Journal Article
%A Le Gonidec, Marion
%T Sur la complexité de mots infinis engendrés par des $q$-automates dénombrables
%J Annales de l'Institut Fourier
%D 2006
%P 2463-2491
%V 56
%N 7
%I Association des Annales de l’institut Fourier
%U https://www.numdam.org/articles/10.5802/aif.2246/
%R 10.5802/aif.2246
%G fr
%F 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) no. 7, pp. 2463-2491. doi : 10.5802/aif.2246. https://www.numdam.org/articles/10.5802/aif.2246/

[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

  • Zhang, Jie-Meng; Chen, Jin; Guo, Ying-Jun; Wen, Zhi-Xiong Morphisms on infinite alphabets, countable states automata and regular sequences, Chaos, Solitons Fractals, Volume 99 (2017), p. 263 | DOI:10.1016/j.chaos.2017.04.018
  • Bibliography, Formal Languages, Automata and Numeration Systems 1 (2014), p. 257 | DOI:10.1002/9781119008200.biblio
  • Bibliography, Formal Languages, Automata and Numeration Systems 2 (2014), p. 193 | DOI:10.1002/9781119042853.biblio
  • Le Gonidec, Marion On the complexity of a family of k-context-free sequences, Theoretical Computer Science, Volume 414 (2012) no. 1, p. 47 | DOI:10.1016/j.tcs.2011.09.022
  • Guay-Paquet, Mathieu; Shallit, Jeffrey Avoiding squares and overlaps over the natural numbers, Discrete Mathematics, Volume 309 (2009) no. 21, p. 6245 | DOI:10.1016/j.disc.2009.06.004
  • Le Gonidec, Marion Drunken man infinite words complexity, RAIRO - Theoretical Informatics and Applications, Volume 42 (2008) no. 3, p. 599 | DOI:10.1051/ita:2008012
  • Le Gonidec, Marion On complexity functions of infinite words associated with generalized Dyck languages, Theoretical Computer Science, Volume 407 (2008) no. 1-3, p. 117 | DOI:10.1016/j.tcs.2008.05.015

Cité par 7 documents. Sources : Crossref