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.

@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
DA  - 2008///
SP  - 599
EP  - 613
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2008012/
UR  - https://www.ams.org/mathscinet-getitem?mr=2434037
UR  - https://doi.org/10.1051/ita:2008012
DO  - 10.1051/ita:2008012
LA  - en
ID  - ITA_2008__42_3_599_0
ER  - 
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 1318964 | Zbl 0803.68094

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

[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 1466182 | Zbl 1096.68690

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

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

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

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

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

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

[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 2290787 | Zbl 1121.68090

[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 2290789 | Zbl 1147.11016

[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 1418316 | Zbl 0868.11004

[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 784265 | Zbl 0554.68053

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

Cité par Sources :