The "runs" conjecture

The "runs" conjecture,10.1016/j.tcs.2010.06.019,Theoretical Computer Science,Maxime Crochemore,Lucian Ilie,Liviu Tinta

The "runs" conjecture   (Citations: 2)
BibTex | RIS | RefWorks Download
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.
Journal: Theoretical Computer Science - TCS , vol. 412, no. 27, pp. 2931-2941, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Their maximal number is an open question ([34]) but tight approximations exist ([48,18])...
    • ...Considering runs having close centres (the beginning position of the second period) the bound has been lowered to 1.6 n in [13,15], improved to 1.52 n in [27], and further to 1.029 n as a result of the computation of a tight approximation of the maximal number of 60-runs (see [18])...

    Golnaz Badkobehet al. Hunting Redundancies in Strings

Sort by: