The maximal number of cubic runs in a word

Maxime Crochemore 1, 2 Costas S. Iliopoulos 2 Marcin Kubica 3 Jakub Radoszewski 3 Wojciech Rytter 3 Tomasz Walen 3
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Informatics
3 Institute of Informatics
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) < 0.5n. The proof of linearity of cubic-runs(n) utilizes only simple properties of Lyndon words and is considerably simpler than the corresponding proof for general runs. For binary words, we provide a better upper bound cubic-runs2(n) < 0.48n which requires computer-assisted verification of a large number of cases. We also construct an infinite sequence of words over a binary alphabet for which the lower bound is 0.41n.
Keywords : Lyndon word Fibonacci word run in a word
Document type :
Journal articles
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download
https://hal-upec-upem.archives-ouvertes.fr/hal-00836960
Contributor : Maxime Crochemore <>
Submitted on : Thursday, April 19, 2018 - 5:06:00 PM
Last modification on : Monday, April 23, 2018 - 10:31:15 AM
Long-term archiving on : Tuesday, September 18, 2018 - 4:11:31 PM

File

cubicruns.pdf
Files produced by the author(s)

Identifiers

Collections

ENPC | LIGM | PARISTECH | INSMI | LIGM_ALGO | UNIV-MLV | UPEC-UPEM | LIGM_MOA

Citation

Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, et al.. The maximal number of cubic runs in a word. Journal of Computer and System Sciences, Elsevier, 2012, 78 (6), pp.1828-1836. ⟨10.1016/j.jcss.2011.12.005⟩. ⟨hal-00836960⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

295

Files downloads

91

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD