- Lyndon word
In
mathematics , in the areas ofcombinatorics andcomputer science , a Lyndon word is a certain type of string over an alphabet. Several equivalent definitions are possible.A "k"-ary Lyndon word of length "n" is an "n"-character string over an alphabet of size "k", and which is the minimal element in the
lexicographical ordering of all its rotations. The minimality implies that a Lyndon word is aperiodic, so differs from any of its non-trivial rotations.Alternately, a Lyndon word has the property that, whenever it is split into two substrings, it is always lexicographically less than the right substring. That is, if "w" is a Lyndon word, and "w"="uv" is any factorization into two substrings, with "u" and "v" understood to be non-empty, then "w" < "v". This definition implies that "w" is a Lyndon word if and only if there exist Lyndon words "u" and "v" such that "u" < "v" and "w"="uv". This property allows the set of all Lyndon words to be generated recursively, whence their importance to computer science.
Lyndon words correspond to aperiodic necklace class representatives and can thus be counted with Moreau's necklace-counting function.
Lyndon words have an application to the description of
free Lie algebra s, in constructing a basis for the homogeneous part of a given degree. Lyndon words may be understood as a special case ofHall set s.A theorem of Radford states that the algebra of
polynomial s of Lyndon words with rational coefficients is ashuffle algebra ; that is, they form analgebra over a ring , with multiplication taken to be the shuffle operator.See also
*
De Bruijn sequence References
*
* Frank Ruskey, " [http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html Info on necklaces, Lyndon words, De Bruijn sequences] ", (2003)
Wikimedia Foundation. 2010.