The Prague Stringology Conference 2006
Frantisek Franek and Qian Yang
An Asymptotic Lower Bound for the Maximal-Number-of-Runs Function
| Abstract: |
| An asymptotic lower bound for the maxrun function r(n) = max {number of runs in string x | all strings x of length n} is presented. More precisely, it is shown that for any ε > 0, (α-ε)n is an asymptotic lower bound, where α = 3/(1+50.5) ≈ 0.927. A recent construction of an increasing sequence of binary strings "rich in runs" is modified and extended to prove the result. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |