# zbMATH — the first resource for mathematics

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.

##### MSC:
 68Q45 Formal languages and automata
Full Text: