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. 029 n. This bound is obtained using a combination of theory and computer verification.

Authors

• Maxime Crochemore
• Lucian Ilie
• Liviu Tinta

Keywords

• Algorithms on strings
• Repetitions
• Runs
• Compression