Drunken man infinite words complexity
Gonidec, Marion Le
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 599-613 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2008-01-01
DOI : https://doi.org/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},
     volume = {42},
     year = {2008},
     pages = {599-613},
     doi = {10.1051/ita:2008012},
     mrnumber = {2434037},
     zbl = {pre05346819},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 599-613. doi : 10.1051/ita:2008012. http://gdmltest.u-ga.fr/item/ITA_2008__42_3_599_0/

[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