This article deals with combinatorial properties of infinite words generated by countable and deterministic -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 .
On étudie, dans cet article, les propriétés combinatoires de mots engendrés à l’aide de -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 .
Mot clés : mots infinis, complexité, substitutions, automates
Keywords: Infinite words, complexity, substitutions, automata
@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 = {http://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 - http://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 http://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, Volume 56 (2006) no. 7, pp. 2463-2491. doi : 10.5802/aif.2246. http://www.numdam.org/articles/10.5802/aif.2246/
[1] Sur la complexité des suites infinies, Bull. Belg. Math. Soc. Simon Stevin, Volume 1 (1994) no. 2, pp. 133-143 | EuDML | MR | Zbl
[2] Automatic sequences. Theory, applications, generalizations, Cambridge University Press, Cambridge, 2003 | MR | Zbl
[3] Theory of codes, Academic Press, 1985 | MR | Zbl
[4] Enumeration of factors in the Thue-Morse word, Discrete Applied Math., Volume 24 (1989), pp. 83-96 | DOI | MR | Zbl
[5] Uniform-tag sequences, Math. Syst. Th., Volume 6 (1972), pp. 164-192 | DOI | MR | Zbl
[6] 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] Automata, languages and machines, A, Academic Press, 1974 | Zbl
[8] Substitution dynamical systems on infinite alphabets (2006) (to appear in Ann. Inst. Fourier) | EuDML | Numdam | MR | Zbl
[9] Combinatorics on words, Encyclopedia of Mathematics and Its applications, 17, Cambridge University Press, 1983 | MR | Zbl
[10] Algebraic combinatorics on words, Encyclopedia of Mathematics and Its applications, 90, Cambridge University Press, 2002 | MR | Zbl
[11] Propriétés arithmétiques des substitutions et automates infinis (2006) (to appear in Ann. Inst. Fourier) | Numdam | MR
[12] 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] Reconnaissabilité des substitutions et complexité des suites automatiques, Bull. Soc. Math. France, Volume 124 (1996) no. 2, pp. 329-346 | Numdam | MR | Zbl
[14] 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] Mots infinis. Technical report 93.40, Laboratoire Informatique Théorique et Programmation. Institut Blaise Pascal, 1997
[16] Infinite words, Automata, Semigroups, Logic and Games, Pure and Applied Mathematics, 141, Elsevier, 2004 | Zbl
[17] 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] Substitution dynamical systems-spectral analysis, Lecture Notes in Mathematics, 1294, Springer-Verlag, Berlin, 1987 | MR | Zbl
[19] Handbook of formal language, Springer-Verlag, 1997 | Zbl
Cited by Sources: