Name
Abstract | ||
|---|---|---|
Since the work of Kolpakov and Kucherov in [5,6], it is known that ρ(n), the maximal number of runs in a string, is linear in the length nof the string. A lower bound of $3/(1 + \sqrt{5})n \sim 0.927n$ has been given by Franek and al. [3,4], and upper bounds have been recently provided by Rytter, Puglisi and al., and Crochemore and Ilie (1.6n) [8.7.1]. However, very few properties are known for the ρ(n)/nfunction. We show here by a simple argument that limn→ ∞ρ(n)/nexists and that this limit is never reached. Moreover, we further study the asymptotic behavior of ρp(n), the maximal number of runs with period at most p. We provide a new bound for some microruns : we show that there is no more than 0.971 nruns of period at most 9 in binary strings. Finally, this technique improves the previous best known upper bound, showing that the total number of runs in a binary string of length nis below 1.52n. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-88282-4_22 | LATA |
Keywords | Field | DocType |
asymptotic behavior,length nof,length ni,maximal number,total number,simple argument,upper bound,binary string,lower bound | Discrete mathematics,Combinatorics,Upper and lower bounds,Binary strings,Asymptotic analysis,Mathematics | Conference |
Volume | ISSN | Citations |
5196 | 0302-9743 | 31 |
PageRank | References | Authors |
1.71 | 7 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mathieu Giraud | 1 | 124 | 15.28 |