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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2005, 290 (1), pp.1-25
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-00619337
Contributeur : Cyril Nicaud <>
Soumis le : mardi 6 septembre 2011 - 10:48:38
Dernière modification le : jeudi 7 février 2019 - 17:48:12
Document(s) archivé(s) le : mercredi 7 décembre 2011 - 02:30:10

Fichiers

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

507

Téléchargements de fichiers

503