The Standard Factorization of Lyndon Words: an Average Point of View

Abstract : A non-empty word w is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization uv where v is its smallest proper suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a twoletter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4.
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619337
Contributor : Cyril Nicaud <>
Submitted on : Tuesday, September 6, 2011 - 10:48:38 AM
Last modification on : Thursday, February 7, 2019 - 5:48:12 PM
Long-term archiving on : Wednesday, December 7, 2011 - 2:30:10 AM

Files

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619337, version 1

Citation

Frédérique Bassino, Julien Clément, Cyril Nicaud. The Standard Factorization of Lyndon Words: an Average Point of View. Discrete Mathematics, Elsevier, 2005, 290 (1), pp.1-25. ⟨hal-00619337⟩

Share

Metrics

Record views

586

Files downloads

718