The Prague Stringology Conference 2008

Wataru Matsubara, Kazuhiko Kusano, Akira Ishino, Hideo Bannai and Ayumi Shinohara

New Lower Bounds for the Maximum Number of Runs in a String

We show a new lower bound for the maximum number of runs in a string. We prove that for any ε > 0, (α - ε) n is an asymptotic lower bound, where α =174719/184973 ≈ 0.944565. It is superior to the previous bound 3/(1+50.5) ≈ 0.927 given by Franěk et al.. Moreover, our construction of the strings and the proof is much simpler than theirs.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentations: Presentation Presentation