Skip to Main content Skip to Navigation
Journal articles

On the density of Lyndon roots in factors

Abstract : This work takes another look at the number of runs that a string may contain and provides an alternative proof for the bound. We also propose another stronger conjecture that states the following: for a fixed order on the alphabet, within every factor of a word there are at most as many occurrences of Lyndon roots corresponding to runs in the word as the length of the factor. Only first occurrences of roots in each run are considered.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01806282
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Friday, June 1, 2018 - 6:33:26 PM
Last modification on : Tuesday, February 15, 2022 - 3:44:46 AM
Long-term archiving on: : Sunday, September 2, 2018 - 3:51:50 PM

File

runs_Lroots.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01806282, version 1

Collections

Citation

Maxime Crochemore, Robert Mercas. On the density of Lyndon roots in factors. Theoretical Computer Science, Elsevier, 2016, 656 part B, pp.234-240. ⟨hal-01806282⟩

Share

Metrics

Record views

23

Files downloads

93