On the maximal sum of exponents of runs in a string

Details On the maximal sum of exponents of runs in a string On the maximal sum of exponents of runs in a string

2010-03-25

arxiv.org/abs/1003.4866v1

Computer Science

Discrete Mathematics

7 pages, 1 figure

Scientific paper

A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition $v$ with a period $p$ such that $2p \le |v|$. The exponent of a run is defined as $|v|/p$ and is $\ge 2$. We show new bounds on the maximal sum of exponents of runs in a string of length $n$. Our upper bound of $4.1n$ is better than the best previously known proven bound of $5.6n$ by Crochemore & Ilie (2008). The lower bound of $2.035n$, obtained using a family of binary words, contradicts the conjecture of Kolpakov & Kucherov (1999) that the maximal sum of exponents of runs in a string of length $n$ is smaller than $2n$

Affiliated with

Also associated with

No associations

Rating

On the maximal sum of exponents of runs in a string does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the maximal sum of exponents of runs in a string, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the maximal sum of exponents of runs in a string will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556320