Abstract | ||
---|---|---|
A run is an inclusion maximal occurrence in a word (as a subinterval) of a factor in which the period repeats at least twice. The maximal number of runs in a word of length n has been thoroughly studied, and is known to be between 0.944n and 1.029n. The proofs are very technical. In this paper we investigate cubic runs, in which the period repeats at least three times. We show the upper bound on their maximal number, cubic-runs(n), in a word of length n: cubic-runs(n) |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.jcss.2011.12.005 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
maximal number,cubic run,length n,inclusion maximal occurrence,lyndon word,fibonacci word | Fibonacci word,Discrete mathematics,Combinatorics,Upper and lower bounds,Sequence,Linearity,Mathematical proof,Lyndon word,Mathematics,Binary number,Alphabet | Journal |
Volume | Issue | ISSN |
78 | 6 | 0022-0000 |
Citations | PageRank | References |
1 | 0.35 | 18 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
maxime crochemore | 1 | 73 | 6.84 |
C. S. Iliopoulos | 2 | 52 | 6.67 |
M. Kubica | 3 | 30 | 2.52 |
jakub radoszewski | 4 | 32 | 2.90 |
wojciech rytter | 5 | 130 | 17.13 |
Tomasz Waleń | 6 | 706 | 39.62 |