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 n-character string over an alphabet of size k, which is the minimal element in lexicographical ordering of all its rotations. The minimality implies that a Lyndon word is aperiodic, not equal to 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.