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 - https://www.scopus.com/pages/publications/67649958682
UR - https://www.scopus.com/pages/publications/67649958682#tab=citedBy
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 -