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

Cassaigne, Julien

Bull. Belg. Math. Soc. - Simon Stevin 4, No. 1, 67-88 (1997).

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)].

Reviewer: J.-P.Allouche (Orsay)

MSC:

68R15	Combinatorics on words
11B85	Automata sequences

Keywords:

subword complexity; substitutive sequences; special factors; automatic sequences; block complexity; combinatorics on words; binary sequence; complexity function

Citations:

Zbl 0683.20045; Zbl 0671.10050; Zbl 0855.68072