Lyndon words with a fixed standard right factor

Abstract : Given a totally ordered alphabet A = {a1 < a2 < < aq}, a Lyndon word is a word that is strictly smaller, for the lexicographical order, than any of its conjugates (i.e., all words obtained by a circular permutation on the letters). Lyndon words were introduced by Lyndon [6] under the name of "standard lexicographic sequences" in order to give a base for the free Lie algebra over A. The set of Lyndon words is denoted by L. For instance, with a binary alphabet A = {a, b}, the first Lyndon words until length five are L = {a, b, ab, aab, abb, aaab, aabb, abbb, aaaab, aaabb, aabab, aabbb, ababb, abbbb, . . . }. Note that a non-empty word is a Lyndon word if and only if it is strictly smaller than any of its proper suffixes.
Type de document :
Communication dans un congrès
Munro J. Ian. 15th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA 2004), Jan 2004, New Orleans, Louisiana, United States. SIAM, pp.646-647, 2004
Liste complète des métadonnées

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

https://hal-upec-upem.archives-ouvertes.fr/hal-00619866
Contributeur : Cyril Nicaud <>
Soumis le : jeudi 6 octobre 2011 - 13:17:08
Dernière modification le : mercredi 11 avril 2018 - 12:12:02
Document(s) archivé(s) le : samedi 7 janvier 2012 - 02:21:57

Fichiers

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

Identifiants

  • HAL Id : hal-00619866, version 1

Collections

Citation

Frédérique Bassino, Julien Clément, Cyril Nicaud. Lyndon words with a fixed standard right factor. Munro J. Ian. 15th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA 2004), Jan 2004, New Orleans, Louisiana, United States. SIAM, pp.646-647, 2004. 〈hal-00619866〉

Partager

Métriques

Consultations de la notice

250

Téléchargements de fichiers

114