Complexity and special factors (Q1280227)

The (block-)complexity \((p(n))\) of an infinite sequence over a finite alphabet is defined by: \(p(n)\) is the number of possible blocks of length \(n\) ocurring in the sequence. A word \(u\) is called special for a sequence defined on \(\{0,1\}\), if \(u\), \(u0\), \(u1\) are all factors (subwords) of the sequence (such a word is also called right-special. Similar definition for left-special). A word is bispecial if it is both right-special and left-special. The author surveys this area of combinatorics on words. He then states several results, in particular. 1) There exists a binary sequence whose complexity is ultimately equal to \(\alpha n+\beta\) if and only if either \(\alpha\in \{0,1\}\) and \(\beta\in \mathbb{N}\setminus\{0\}\), or \(\alpha\in \mathbb{N}\setminus \{0,1\}\) and \(\beta\in\mathbb{Z}\). 2) There exists a sequence with complexity \(p(n)= \alpha n+\beta\), \(\forall n\geq 1\) for \((\alpha,\beta)\in \mathbb{N}\times \mathbb{Z}\) if and only if \(\alpha+\beta\geq 1\) and \(2\alpha+ \beta\leq(\alpha+ \beta)^2\). 3) The complexity function of a sequence satisfies \(p(n)= O(n)\) if and only if \(p(n+ 1)- p(n)= O(1)\). (The proof of this last result is given in another paper of the author.) Note that the complexity function of the Thue-Morse sequence was computed independently by \textit{S. Brolek} [Discrete Appl. Math. 24, No. 1-3, 83-96 (1989; Zbl 0683.20045)] and \textit{A. de Luca} and \textit{S. Varricchio} [Theor. Comput. Sci. 63, No. 3, 333-348 (1989; Zbl 0671.10050)]. Note also that Reference [11] appeared: \textit{B. Mossé}, Reconnaissabilité des substitutions et complexite des suites automatiques, Bull. Soc. Math. Fr. 124, 329-346 (1996; Zbl 0855.68072)].