## Complexity and special factors. (Complexité et facteurs spéciaux.)(French)Zbl 0921.68065

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 S. Brolek [Discrete Appl. Math. 24, No. 1-3, 83-96 (1989; Zbl 0683.20045)] and A. de Luca and S. Varricchio [Theor. Comput. Sci. 63, No. 3, 333-348 (1989; Zbl 0671.10050)].
Note also that Reference [11] appeared: B. Mossé, Reconnaissabilité des substitutions et complexite des suites automatiques, Bull. Soc. Math. Fr. 124, 329-346 (1996; Zbl 0855.68072)].

### MSC:

 68R15 Combinatorics on words 11B85 Automata sequences

### Citations:

Zbl 0683.20045; Zbl 0671.10050; Zbl 0855.68072
Full Text: