Lyndon word
From Wikipedia, the free encyclopedia
In mathematics, in the areas of combinatorics and computer 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 algebras, in constructing a basis for the homogeneous part of a given degree. Lyndon words may be understood as a special case of Hall sets.
A theorem of Radford states that the algebra of polynomials of Lyndon words with rational coefficients is a shuffle algebra; that is, they form an algebra over a ring, with multiplication taken to be the shuffle operator.
[edit] See also
[edit] References
- G. Melançon (2001), “Lyndon word”, in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104
- Frank Ruskey, Info on necklaces, Lyndon words, De Bruijn sequences, (2003)
