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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619866
Contributor : Cyril Nicaud <>
Submitted on : Thursday, October 6, 2011 - 1:17:08 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:02 PM
Long-term archiving on : Saturday, January 7, 2012 - 2:21:57 AM

Files

hal.pdf
Files produced by the author(s)

Identifiers

  • 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. 15th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA 2004), Jan 2004, New Orleans, Louisiana, United States. pp.646-647. ⟨hal-00619866⟩

Share

Metrics

Record views

273

Files downloads

115