Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Cyril Nicaud Connect in order to contact the contributor
Submitted on : Thursday, October 6, 2011 - 1:17:08 PM
Last modification on : Wednesday, January 19, 2022 - 4:42:04 PM
Long-term archiving on: : Saturday, January 7, 2012 - 2:21:57 AM


Files produced by the author(s)


  • HAL Id : hal-00619866, version 1



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⟩



Record views


Files downloads