In mathematics, in the areas of combinatorics and computer science, a Lyndon word is a nonempty string that is strictly smaller in lexicographic order than all of its rotations.
, and which is the unique minimum element in the lexicographical ordering in the multiset of all its rotations.
is a Lyndon word if and only if it is nonempty and lexicographically strictly smaller than any of its proper suffixes, that is
[5] The Lyndon words over the two-symbol binary alphabet {0,1}, sorted by length and then lexicographically within each length class, form an infinite sequence that begins The first string that does not belong to this sequence, "00", is omitted because it is periodic (it consists of two repetitions of the substring "0"); the second omitted string, "10", is aperiodic but is not minimal in its permutation class as it can be cyclically permuted to the smaller string "01".
The empty string also meets the definition of a Lyndon word of length zero.
The numbers of binary Lyndon words of each length, starting with length zero, form the integer sequence Lyndon words correspond to aperiodic necklace class representatives and can thus be counted with Moreau's necklace-counting function.
[3][6] Duval (1988) provides an efficient algorithm for listing the Lyndon words of length at most
, then the steps are: The worst-case time to generate the successor of a word
However, if the words being generated are stored in an array of length
[7] A constant fraction of the words in this sequence have length exactly
, so the same procedure can be used to efficiently generate words of length exactly
, by filtering out the generated words that do not fit these criteria.
According to the Chen–Fox–Lyndon theorem, every string may be formed in a unique way by concatenating a sequence of Lyndon words, in such a way that the words in the sequence are nonincreasing lexicographically.
[8] The final Lyndon word in this sequence is the lexicographically smallest suffix of the given string.
[9] Lyndon factorizations may be used as part of a bijective variant of the Burrows–Wheeler transform for data compression,[10] and in algorithms for digital geometry.
[11] Such factorizations can be written (uniquely) as finite binary trees, with the leaves labelled by the alphabet, with each rightward branch given by the final Lyndon word in the sequence.
[12] Such trees are sometimes called standard bracketings and can be taken as factorization of the elements of a free group or as the basis elements for a free Lie algebra.
These trees are a special case of Hall trees (as Lyndon words are a special case of Hall words), and so likewise, the Hall words provide a standard order, called the commutator collecting process for groups, and basis for Lie algebras.
Duval (1983) developed an algorithm for finding the standard factorization that runs in linear time and constant space.
It iterates over a string trying to find as long a Lyndon word as possible.
When it finds one, it adds it to the result list and proceeds to search the remaining part of the string.
Given a string S of length N, one should proceed with the following steps: If one concatenates together, in lexicographic order, all the Lyndon words that have length dividing a given number n, the result is a de Bruijn sequence, a circular sequence of symbols such that each possible length-n sequence appears exactly once as one of its contiguous subsequences.
For example, the concatenation of the binary Lyndon words whose length divides four is This construction, together with the efficient generation of Lyndon words, provides an efficient method for constructing a particular de Bruijn sequence in linear time and logarithmic space.
[14] Lyndon words have an application to the description of free Lie algebras, in constructing a basis for the homogeneous part of a given degree; this was Lyndon's original motivation for introducing these words.
[4] Lyndon words may be understood as a special case of Hall sets.
[4] For prime p, the number of irreducible monic polynomials of degree d over the field
is the same as the number of Lyndon words of length d in an alphabet of p symbols; they can be placed into explicit correspondence.
More precisely, let A be an alphabet, let k be a field of characteristic 0 (or, more general, a commutative ℚ-algebra), and let R be the free noncommutative k-algebra k ⟨ xa | a ∈ A ⟩.
Thus, the words over A form a k-vector space basis of R. Then, a shuffle product is defined on R; this is a k-bilinear, associative and commutative product, which is denoted by ш, and which on the words can be recursively defined by The shuffle algebra on the alphabet A is defined to be the additive group R endowed with ш as multiplication.
Radford's theorem[16] now states that the Lyndon words are algebraically independent elements of this shuffle algebra, and generate it; thus, the shuffle algebra is isomorphic to a polynomial ring over k, with the indeterminates corresponding to the Lyndon words.