On the density of Lyndon roots in factors

Maxime Crochemore (1, 2) , Robert Mercas (1, 3)

1 Department of Informatics [King's College London]
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 CAU - Christian-Albrechts-Universität zu Kiel = Christian-Albrechts University of Kiel = Université Christian-Albrechts de Kiel

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.

Mots clés: Runs; Lyndon words; Lyndon roots; Critical factorisation

Domaines: Algorithme et structure de données [cs.DS]

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