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
| Abstract: |
| 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: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentations: |  |
|