Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. (English) Zbl 0671.10050

de Luca, Aldo; Varricchio, Stefano

Theor. Comput. Sci. 63, No. 3, 333-348 (1989).

The (Prouhet)-Thue-Morse sequence is one of the fixed points of the morphism \(a\to ab\), \(b\to ba\). The authors define \(\phi\) (n) to be the number of factors w of the Thue-Morse sequence such that both wa and wb are factors, (“special factors”). They then prove that \(\phi\) (n) is equal either to 2 or to 4 for \(n\geq 1\). They also characterize those n such that \(\phi (n)=2\) and give an algorithm to construct all special factors of given length.
Denoting by F(n) the total number of factors of length n (in the Thue- Morse sequence), they deduce the exact value of F(n) (using the relation \(F(n+1)=F(n)+\phi (n))\), and obtain the inequalities \(3n\leq F(n+1)\leq 10n/3.\) (Note that every automatic sequence satisfies F(n)\(\leq Cn\), see A. Cobham, Math. Syst. Theory 6, 164-192 (1972; Zbl 0253.02029). As a consequence they prove that the Thue-Morse monoid is finitely generated, periodic, infinite and weakly permutable.
Note, as the authors point out, that an enumeration formula for the factors of the Thue-Morse sequence has been independently obtained by S. Brlek [Enumeration of factors in the Thue-Morse word, in Proc. Coll. Montréalais sur la Combinatoire et l’Informatique (to appear)].

Reviewer: J.-P.Allouche

MSC:

11B99	Sequences and sets
68Q45	Formal languages and automata
20M10	General structure theory for semigroups

Keywords:

Thue-Morse sequence; weakly permutable monoid; algorithm; special factors of given length; total number of factors; Thue-Morse monoid; enumeration formula

Citations:

Zbl 0253.02029

References:

[1]	Berstel, J.; de Fibonacci, Mots, (Seminaire d’Informatique Théorique (1980/81), L.I.T.P. Université Paris VI et VII), 57-78, Année
[2]	Berstel, J.; Crochemore, M.; Pin, J. E., Thue-Morse sequence and p-adic Technology of free monoid (February 1987), L.I.T.P., Université Paris VI et VII, preprint.
[3]	Blyth, R. D., Rewriting products of groups elements, (Ph.D. Thesis (1987), University of Illinois at Urbana-Champain) · Zbl 0647.20033
[4]	de Luca, A.; Yarricchio, S., On special factors of the Thue-Morse sequence on three symbols, Inform. Process Lett., 27, 281-285 (1988)
[5]	Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[6]	Morse, M.; Hedlund, G., Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. J., 11, 1-7 (1944) · Zbl 0063.04115
[7]	Pansiot, J. J., The Morse sequence and iterated morphisms, Inform. Process. Lett., 12, 68-70 (1981) · Zbl 0464.68075
[8]	Pirillo, G., On permutation properties for finitely generated semigroups, (Proc. Conf. on Combinatorics 1986 (July 1986), Passo della Mendola: Passo della Mendola Italy) · Zbl 0654.20068
[9]	Restivo, A.; Reutenauer, C., On the Burnside problem for semigroups, J. of Algebra, 89, 102-104 (1984) · Zbl 0545.20051
[10]	Restivo, A.; Salemi, S., Overlap-free words on two symbols, (Lecture Notes in Computer Science, 192 (1985), Springer: Springer Berlin), 198-206, Automata on Infinite Words · Zbl 0572.20038
[12]	Thue, A., Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl., Christiana, 7, 1-22 (1906) · JFM 39.0283.01
[13]	Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Kl., Christiana, 1 (1912) · JFM 44.0462.01