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

Wataru Matsubara; Kazuhiko Kusano; Akira Ishino; Hideo Bannai; Ayumi Shinohara

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

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

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

31 Citations (Scopus)

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 + √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.

Original language	English
Title of host publication	Proceedings of the Prague Stringology Conference 2008
Pages	140-145
Number of pages	6
Publication status	Published - 2008
Event	Prague Stringology Conference 2008, PSC 2008 - Prague, Czech Republic Duration: Sept 1 2008 → Sept 3 2008

Other

Other	Prague Stringology Conference 2008, PSC 2008
Country/Territory	Czech Republic
City	Prague
Period	9/1/08 → 9/3/08

All Science Journal Classification (ASJC) codes

Mathematics(all)

Cite this

@inproceedings{41fa0377a46f40e785aca0a9b9675b46,

title = "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 + √5) ≈ 0.927 given by Fran{\v e}k et al. [6,7]. Moreover, our construction of the strings and the proof is much simpler than theirs.",

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

year = "2008",

language = "English",

isbn = "9788001041451",

pages = "140--145",

booktitle = "Proceedings of the Prague Stringology Conference 2008",

note = "Prague Stringology Conference 2008, PSC 2008 ; Conference date: 01-09-2008 Through 03-09-2008",

}

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

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 -

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

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this