Séminaire Lotharingien de Combinatoire, B17f (1987), 12 pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1987, 348/S-17, p.
129-140.]
Srečko Brlek
>On Word Chains
Abstract.
Word chains are an extension of addition chains to words. Over
a q-letter alphabet, any long enough word admits a word chain
of length at most
(l+ε)n/logq(n), for a fixed
and arbitrary
ε>0; moreover, there exist words with no chain shorter than
n/logq-1(n). We study word chains for
the Thue-Morse M word with a representation by binary trees. A
conjecture on the enumeration of shortest word chains computing M
is proposed.
The following version is available: