Complexity of Toeplitz sequences
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].
- Enumeration of factors in the Thue-Morse word
- Le p-pliage de papier
- Sequences with minimal block growth
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- Symbolic Dynamics II. Sturmian Trajectories
- The number of factors in a paperfolding sequence
- The tower of Hanoi
- Toeplitz sequences, paperfolding, towers of Hanoi and progression-free sequences of integers
- Tours de Hanoï et automates
- On the infinite permutation generated by the period doubling word
- Uniform sets and complexity
- About the p-paperfolding words
- On a conjecture on bidimensional words.
- Complexity of Hartman sequences
- Language structure of pattern Sturmian words
- Words with unbounded periodicity complexity
- Toeplitz sequences of intermediate complexity
- On possible growths of arithmetical complexity
- Sequences of low arithmetical complexity
- Constructing partial words with subword complexities not achievable by full words
- Algorithmic combinatorics on partial words
- Combinatorics of one-dimensional simple Toeplitz subshifts
- On possible growths of Toeplitz languages
- Sequences of linear arithmetical complexity
- On the structure of generic subshifts
- Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions
This page was built for publication: Complexity of Toeplitz sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1382825)
