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

De Luca, Aldo; Varricchio, Stefano

Inf. Process. Lett. 27, No. 6, 281-285 (1988).

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.

MSC:

68R15	Combinatorics on words
68Q45	Formal languages and automata

Keywords:

square-free word; special factor; structure-function

Citations:

Zbl 0671.10050

References:

[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