The "runs" conjecture
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. (C) 2010 Elsevier B.V. All rights reserved.
runs repetitions algorithms on strings compression