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

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


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


Zbl 0253.02029
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.