Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Cyril Nicaud Connect in order to contact the contributor
Submitted on : Tuesday, September 6, 2011 - 10:48:38 AM
Last modification on : Saturday, June 25, 2022 - 9:46:42 AM
Long-term archiving on: : Wednesday, December 7, 2011 - 2:30:10 AM


Files produced by the author(s)



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. ⟨10.1016/j.disc.2004.11.002⟩. ⟨hal-00619337⟩



Record views


Files downloads