×

Drunken man infinite words complexity. (English) Zbl 1188.68217

The author, continuing her study of infinite words over a finite alphabet that are generated by deterministic complete countable automata (or equivalently by constant length substitutions over a countable alphabet) computes the block-complexity of the so-called “drunken man infinite words”. She proves that the block-complexity of these words is equivalent to \(n\left(\frac{\log n}{\log 2}\right)^2\) when \(n\) goes to infinity.

MSC:

68R15 Combinatorics on words
11B85 Automata sequences
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

References:

[1] J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. Simon Stevin1 (1994) 133-143. · Zbl 0803.68094
[2] J.-P. Allouche and J. Shallit, Automatic sequences. Theory, applications, generalizations. Cambridge University Press (2003). · 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. Zbl1096.68690 · Zbl 1096.68690
[4] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67-88. · Zbl 0921.68065
[5] A. Cobham, Uniform-tag sequences. Math. Syst. Theory6 (1972) 164-192. · Zbl 0253.02029
[6] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145-154. · Zbl 0936.37008
[7] S. Ferenczi, Substitution dynamical systems on infinite alphabets. Ann. Inst. Fourier56 (2006) 2315-2343. · Zbl 1147.37007
[8] E. Fouvry and C. Mauduit, Sur les entiers dont la somme des chiffres est moyenne. J. Number Theory114 (2005) 135-152. · Zbl 1084.11045
[9] P. Kůrka, Topological and symbolic dynamics, Cours spécialisés Vol. 11, SMF (2003). · Zbl 1038.37011
[10] M. Le Gonidec, Sur la complexité de mots infinis engendrés par des q-automates dénombrables. Ann. Inst. Fourier56 (2006) 2463-2491. Zbl1121.68090 · Zbl 1121.68090
[11] M. Le Gonidec, Sur la complexité des mots q\infty -automatiques. Ph.D. thesis, Université Aix-Marseille II (2006).
[12] C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis. Ann. Inst. Fourier56 (2006) 2525-2549. Zbl1147.11016 · 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 Theory61 (1996) 25-38. Zbl0868.11004 · 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). · Zbl 0554.68053
[15] L. Staiger, Kolmogorov complexity of infinite words. CDMTCS Research Report Series279 (2006). · Zbl 1124.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.