The Standard Factorization of Lyndon Words: an Average Point of View - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2005

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

Résumé

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.
Fichier principal
Vignette du fichier
hal.pdf (253.36 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00619337 , version 1 (06-09-2011)

Identifiants

Citer

Frédérique Bassino, Julien Clément, Cyril Nicaud. The Standard Factorization of Lyndon Words: an Average Point of View. Discrete Mathematics, 2005, 290 (1), pp.1-25. ⟨10.1016/j.disc.2004.11.002⟩. ⟨hal-00619337⟩
231 Consultations
1307 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More