A Different Proof of the Crochemore-Ilie Lemma Concerning Microruns

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F09%3A00160094" target="_blank" >RIV/68407700:21240/09:00160094 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
A Different Proof of the Crochemore-Ilie Lemma Concerning Microruns
Original language description
In a resent paper, Crochemore and Ilie improved the upper bound of the maxrun function ro(n)=max{r(x) : |x| = n}, where r(x) denotes the number of runs in a string x, to 1.6n (computational results on Ilie's web page claim the improvement to 1.048n.) Their proof is essentially in two major steps: first step shows that there is at most 1center of a d-run on average in each interval of length d, in the second step they showed that ro9(n) <= n, where ro9(n) is the count limited to runs of size <= 9. The proof of ro9(n) <= n they presented relies on computation. We present an alternative simpler proof, also computational, to provide an independent verification of Crochemore-Ilie's result. The method used is completely different and has a potential to be verified without an aid of computer.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA201%2F09%2F0807" target="_blank" >GA201/09/0807: String and tree analysis and processing</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)