On generalized words of Thue-Morse.

*(English)*Zbl 0556.68042
Mathematical foundations of computer science, Proc. 11th Symp., Praha/Czech. 1984, Lect. Notes Comput. Sci. 176, 232-239 (1984).

From the text: [For the entire collection see Zbl 0544.00022.]

The existence of infinite words over a three-letter alphabet was shown by A. Thue in 1912 [Norske Vid. Selsk. Skr., Mat. Nat. Kl. 1, No. 1, 1–67 (1912; JFM 44.0462.01)]. The construction of one such word was based on an infinite word \(t\) over the alphabet \(\{0,1\}\), not containing a factor of the form \(xvxvx\), \(x\) being a letter and \(v\) a word. The \(i\)-th symbol of \(t\) can be described as the parity of occurrences of the symbol 1 in the binary expansion of \(i\). The same word \(t\) has been described also by H. M. Morse in 1921 [Trans. Am. Math. Soc. 22, 84–100 (1921; JFM 48.0786.06)].

In the presented paper a class of generalized words of Thue-Morse is investigated. In such a generalized word the \(i\)-th symbol denotes the parity of occurrences of some fixed factor \(w\) over \(\{0,1\}\) in the binary expansion of \(i\). All these generalised words are tag sequences in the sense of Cobham. It is shown that there are no factors of the form \((xv)^ kx\), where \(k=2^{| w|}\) in such a generalized word. Moreover, necessary conditions for appearing of a factor \((xv)^ k\) are given.

The existence of infinite words over a three-letter alphabet was shown by A. Thue in 1912 [Norske Vid. Selsk. Skr., Mat. Nat. Kl. 1, No. 1, 1–67 (1912; JFM 44.0462.01)]. The construction of one such word was based on an infinite word \(t\) over the alphabet \(\{0,1\}\), not containing a factor of the form \(xvxvx\), \(x\) being a letter and \(v\) a word. The \(i\)-th symbol of \(t\) can be described as the parity of occurrences of the symbol 1 in the binary expansion of \(i\). The same word \(t\) has been described also by H. M. Morse in 1921 [Trans. Am. Math. Soc. 22, 84–100 (1921; JFM 48.0786.06)].

In the presented paper a class of generalized words of Thue-Morse is investigated. In such a generalized word the \(i\)-th symbol denotes the parity of occurrences of some fixed factor \(w\) over \(\{0,1\}\) in the binary expansion of \(i\). All these generalised words are tag sequences in the sense of Cobham. It is shown that there are no factors of the form \((xv)^ kx\), where \(k=2^{| w|}\) in such a generalized word. Moreover, necessary conditions for appearing of a factor \((xv)^ k\) are given.

##### MSC:

68Q45 | Formal languages and automata |