On the factors of the Thue-Morse word on three symbols. (English) Zbl 0746.68067

Summary: Let \(m\) be the Thue-Morse word in a three-letter alphabet. A finite factor \(v\) of \(m\) is called special if there exist two distinct letters \(x\), \(y\) of the alphabet such that \(vx\) and \(vy\) are factors of \(m\). Define, for each \(n>0\), \(\psi(n)\) (respectively \(g(n)\)) to be the number of special factors (respectively factors) of length \(n\). By using some of our previous results Aldo De Luca and Stefano Varricchio [Theor. Comput. Sci. 63(3), 333-348 (1989; Zbl 0671.10050)] on the Thue- Morse word on two symbols we prove the following proposition: For each \(n>0\), \(\psi(n)=4\) if \(n\leq3\times 2^{[\log_ 2n]-1}-1\), and \(\psi(n)=2\) otherwise (where \([x]\) is the integer part of \(x\)). As a corollary one has: For each \(n>1\), \(g(n)=4n-2^{[\log_ 2n]}\) if \(n\leq 3\times 2^{[\log_ 2n]-1}\) and \(g(n)=2n+2^{[\log_ 2n]+1}\) otherwise.


68R15 Combinatorics on words
68Q45 Formal languages and automata


Zbl 0671.10050
Full Text: DOI


[1] Berstel, J., Mots de Fibonacci, (Seminaire d’Informatique Théorique (1980/81), Univ. Paris VI and VII), 57-78, L.I.T.P.
[2] Berstel, J.; Crochemore, M.; Pin, J. E., Thue-Morse Sequence and p-adic Technology of Free Monoid (February 1987), Univ. Paris VI and VII, Preprint, L.I.T.P.
[4] de Luca, A.; Varricchio, S., Some Combinatorial Properties of the Thue-Morse Sequence and a Problem in Semigroups (June 1987), Dept. of Mathematics, Univ. of Rome “La Sapienza”, Preprint
[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] Thue, A., Über unendlichen Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 7, 1-22 (1906) · JFM 39.0283.01
[9] Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 1, 1-67 (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.