Journal article
The “runs” conjecture
Abstract
The “runs” conjecture, proposed by Kolpakov and Kucherov (1999) [7], states that the number of occurrences of maximal repetitions (runs) in a string of length n, runs(n), is at most n. We almost solve the conjecture by proving that runs(n)⩽1.029n. This bound is obtained using a combination of theory and computer verification.
Authors
Crochemore M; Ilie L; Tinta L
Journal
Theoretical Computer Science, Vol. 412, No. 27, pp. 2931–2941
Publisher
Elsevier
Publication Date
June 2011
DOI
10.1016/j.tcs.2010.06.019
ISSN
0304-3975