Name
Abstract | ||
|---|---|---|
A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition v with a period p such that 2p≤|v|. The maximal number of runs in a string of length n has been thoroughly studied, and is known to be between 0.944 n and 1.029 n. In this paper we investigate cubic runs, in which the shortest period p satisfies 3p≤|v|. We show the upper bound of 0.5 n on the maximal number of such runs in a string of length n, and construct an infinite sequence of words over binary alphabet for which the lower bound is 0.406 n. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13089-2_19 | LATA |
Keywords | Field | DocType |
binary alphabet,maximal number,cubic run,repetition v,period p,length n,infinite sequence,shortest period p satisfies,inclusion maximal occurrence,satisfiability,upper bound,lower bound | Discrete mathematics,Combinatorics,Sequence,Upper and lower bounds,Mathematics,Alphabet,Binary number | Conference |
Volume | ISSN | ISBN |
6031 | 0302-9743 | 3-642-13088-7 |
Citations | PageRank | References |
198 | 6.46 | 17 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas Iliopoulos | 2 | 497 | 17.26 |
| Marcin Kubica | 3 | 629 | 29.26 |
| Jakub Radoszewski | 4 | 624 | 50.36 |
| Wojciech Rytter | 5 | 2290 | 181.52 |
| Tomasz Waleń | 6 | 706 | 39.62 |