Complexity of Toeplitz sequences (Q1382825)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Complexity of Toeplitz sequences
scientific article

    Statements

    Complexity of Toeplitz sequences (English)
    0 references
    0 references
    20 September 1998
    0 references
    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].
    0 references
    entropy of sequences
    0 references
    Toeplitz sequences
    0 references
    periodic sequences
    0 references
    block complexity
    0 references

    Identifiers