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, (), 157-162
[2] A. Cardon and M. Crochemore, Partitioning a graph in O(⋎A⋎log_{2}⋎V⋎), Theoret. Comput. Sci., to appear. · Zbl 0478.68067
[3] A. Ehrenfeucht and G. Rosenburg, On the separating power of EOL systems, RAIRO, to appear.
[4] Harrison, M.A., Introduction to formal language theory, (1978), 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, (), 128-144 · Zbl 0221.20076
[7] Ross, R.; Winklmann, R., Repetitive strings are not context-free, (1981), Washington State University Pullman, WA, CS-81-070
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.