Complexity of Toeplitz sequences (Q1382825): Difference between revisions

Toeplitz sequences are obtained by iterated insertions of periodic sequences ``with holes'' into periodic sequences ``with holes''. The author computes the block complexity (i.e., the number of blocks of length \(n\)) for a class of Toeplitz sequences. He obtains the following nice consequences. For any rational \(\alpha>1\) there exists a Toeplitz sequence with complexity of the order of \(n^\alpha\); there exist Toeplitz sequences with zero entropy but with complexity larger than any polynomial function. Note that Reference [1] appeared [\textit{J.-P. Allouche}, Bull. Belg. Math. Soc. -- Simon Stevin 1, 133-143 (1994; Zbl 0803.68094)] and that Reference [4] also appeared [the reviewer, Theor. Comput. Sci. 129, 263-278 (1994; Zbl 0820.11011)]. Two more remarks: the title of Reference [7] [\textit{E. M. Coven} and \textit{G. A. Hedlund}, Math. System Theory 7, 138-153 (1973; Zbl 0256.54028)] should be changed into ``Sequences with minimal block growth''; on page 165, just before Example 1, the second quotation of Reference [7] should be replaced by [1].