An optimal algorithm for computing the repetitions in a word. (English) Zbl 0467.68075


68T99 Artificial intelligence
68R99 Discrete mathematics in relation to computer science
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
Full Text: DOI


[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms, ((1974), Addison-Wesley: Addison-Wesley MA), 157-162
[4] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley MA · Zbl 0411.68058
[5] Knuth, D. E.; Morris, J. H.; Pratt, V. R., Fast patternmatching in strings, SIAM J. Comput., 6, 323-350 (1977) · Zbl 0372.68005
[6] Lentin, A.; Schutzenberger, M. P., A combinatorial problem in the theory of free monoids, (Combinatorial Mathematics and Its Applications (1969), University of North Carolina Press: University of North Carolina Press NC), 128-144 · Zbl 0221.20076
[7] Ross, R.; Winklmann, R., Repetitive strings are not context-free (1981), Washington State University: Washington State University Pullman, WA, CS-81-070 · Zbl 0489.68071
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.