The average lengths of the factors of the standard factorization of Lyndon words

Frédérique Bassino 1 Julien Clément 1 Cyril Nicaud 1
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
Abstract : A non-empty word w of {a; b}* 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 suÆx. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is rational and compute explicitly the associated generating function. Next we establish that, for the uniform distribution over the Lyndon words of length n, the average length of the right factor v of the standard factorization is asymptotically 3n/4. Finally we present algorithms on Lyndon words derived from our work together with experimental results.
Type de document :
Communication dans un congrès
Ito Masami and Toyama Masafumi. 6th International Conference on Developments in Language Theory (DLT 2002), Sep 2003, Kyoto, Japan. Springer-Verlag, 2450, pp.307-318, 2003, LNCS
Liste complète des métadonnées
https://hal-upec-upem.archives-ouvertes.fr/hal-00619865
Contributeur : Cyril Nicaud <>
Soumis le : jeudi 6 octobre 2011 - 13:24:49
Dernière modification le : mercredi 11 avril 2018 - 12:12:02
Document(s) archivé(s) le : samedi 7 janvier 2012 - 02:21:52

Fichiers

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

Identifiants

  • HAL Id : hal-00619865, version 1

Collections

UNIV-MLV | LIGM_ALGO | LIGM | ENPC | PARISTECH | UPEC-UPEM

Citation

Frédérique Bassino, Julien Clément, Cyril Nicaud. The average lengths of the factors of the standard factorization of Lyndon words. Ito Masami and Toyama Masafumi. 6th International Conference on Developments in Language Theory (DLT 2002), Sep 2003, Kyoto, Japan. Springer-Verlag, 2450, pp.307-318, 2003, LNCS. 〈hal-00619865〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

237

Téléchargements de fichiers

85

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD