TY - GEN

T1 - New lower bounds for the maximum number of runs in a string

AU - Matsubara, Wataru

AU - Kusano, Kazuhiko

AU - Ishino, Akira

AU - Bannai, Hideo

AU - Shinohara, Ayumi

PY - 2008

Y1 - 2008

N2 - 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 + √5) ≈ 0.927 given by Franěk et al. [6,7]. Moreover, our construction of the strings and the proof is much simpler than theirs.

AB - 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 + √5) ≈ 0.927 given by Franěk et al. [6,7]. Moreover, our construction of the strings and the proof is much simpler than theirs.

UR - http://www.scopus.com/inward/record.url?scp=67649958682&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67649958682&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:67649958682

SN - 9788001041451

T3 - Proceedings of the Prague Stringology Conference 2008

SP - 140

EP - 145

BT - Proceedings of the Prague Stringology Conference 2008

T2 - Prague Stringology Conference 2008, PSC 2008

Y2 - 1 September 2008 through 3 September 2008

ER -