## On the length of word chains.(English)Zbl 0654.68096

Word chains are an extension of addition chains to words. We show that over a q-letter alphabet, any long enough word admits a word chain of length at most $$(1+\epsilon)n/\log_ q n$$, for a fixed arbitrary $$\epsilon >0$$; there exist words with no chain shorter than $$n/\log_{q- 1} n$$. Several examples are given. Finally, we show that words with few factors have short chains.

### MSC:

 68Q45 Formal languages and automata 68Q42 Grammars and rewriting systems