Drunken man infinite words complexity
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 599-613.

In this article, we study the complexity of drunken man infinite words. We show that these infinite words, generated by a deterministic and complete countable automaton, or equivalently generated by a substitution over a countable alphabet of constant length, have complexity functions equivalent to n(log 2 n) 2 when n goes to infinity.

DOI : 10.1051/ita:2008012
Classification : 11B85, 68R15 
@article{ITA_2008__42_3_599_0,
     author = {Gonidec, Marion Le},
     title = {Drunken man infinite words complexity},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {599--613},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     year = {2008},
     doi = {10.1051/ita:2008012},
     mrnumber = {2434037},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2008012/}
}
TY  - JOUR
AU  - Gonidec, Marion Le
TI  - Drunken man infinite words complexity
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
SP  - 599
EP  - 613
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2008012/
DO  - 10.1051/ita:2008012
LA  - en
ID  - ITA_2008__42_3_599_0
ER  - 
%0 Journal Article
%A Gonidec, Marion Le
%T Drunken man infinite words complexity
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 599-613
%V 42
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2008012/
%R 10.1051/ita:2008012
%G en
%F ITA_2008__42_3_599_0
Gonidec, Marion Le. Drunken man infinite words complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 599-613. doi : 10.1051/ita:2008012. http://www.numdam.org/articles/10.1051/ita:2008012/

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

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

[3] J. Cassaigne, Special factors of sequences with linear subword complexity. In Developments in language theory (Magdeburg, 1995), World Sci. Publishing (1996) 25-34. | MR | Zbl

[4] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | MR | Zbl

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

[6] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | MR | Zbl

[7] S. Ferenczi, Substitution dynamical systems on infinite alphabets. Ann. Inst. Fourier 56 (2006) 2315-2343. | Numdam | MR | Zbl

[8] E. Fouvry and C. Mauduit, Sur les entiers dont la somme des chiffres est moyenne. J. Number Theory 114 (2005) 135-152. | MR | Zbl

[9] P. Kůrka, Topological and symbolic dynamics, Cours spécialisés Vol. 11, SMF (2003). | MR | Zbl

[10] M. Le Gonidec, Sur la complexité de mots infinis engendrés par des q-automates dénombrables. Ann. Inst. Fourier 56 (2006) 2463-2491. | Numdam | MR | Zbl

[11] M. Le Gonidec, Sur la complexité des mots q ∞ -automatiques. Ph.D. thesis, Université Aix-Marseille II (2006).

[12] C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis. Ann. Inst. Fourier 56 (2006) 2525-2549. | Numdam | MR | Zbl

[13] C. Mauduit and A. Sárközy, On the arithmetic structure of sets characterized by sum of digits properties. J. Number Theory 61 (1996) 25-38. | MR | Zbl

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

[15] L. Staiger, Kolmogorov complexity of infinite words. CDMTCS Research Report Series 279 (2006). | MR

Cité par Sources :