×

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
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Diwan, A. A., A new combinatorial complexity measure for languages (1986), Computer Science Group, Tata Institute: Computer Science Group, Tata Institute Bombay, India, Rept.
[2] Knuth, D. E., The Art of Computer Programming, (Seminumerical Algorithms, Vol. 2 (1969), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0191.17903
[3] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: 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, (Perrin, D., Automata on Infinite Words. Automata on Infinite Words, Lecture Notes in Computer Science, Vol. 192 (1985), Springer: Springer Berlin), 198-206 · Zbl 0572.20038
[6] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.