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.


68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
Full Text: DOI


[1] Diwan, A.A., A new combinatorial complexity measure for languages, (1986), Computer Science Group, Tata Institute Bombay, India, Rept.
[2] Knuth, D.E., The art of computer programming, () · Zbl 0191.17903
[3] Lothaire, M., Combinatorics on words, (1983), Addison-Wesley Reading, MA · Zbl 0514.20045
[4] Restivo, A.; Salemi, S., On weakly square free words, Bull. EATCS, 21, 49-56, (1983)
[5] Restivo, A.; Salemi, S., Overlap free words on two symbols, (), 198-206
[6] Rozenberg, G.; Salomaa, A., The mathematical theory of L systems, (1980), Academic Press New York · Zbl 0365.68072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.