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. Lyndon words are named after mathematician Roger Lyndon, who investigated them in 1954, calling them standard lexicographic sequences. Anatoly Shirshov introduced Lyndon words in 1953 calling them regular words. Lyndon words are a special case of Hall words; almost all properties of Lyndon words are shared by Hall words.
Definitions
Several equivalent definitions exist.
A -ary Lyndon word of length is an -character string over an alphabet of size , and which is the unique minimum element in the lexicographical ordering in the multiset of all its rotations. Being the singularly smallest rotation implies that a Lyndon word differs from any of its non-trivial rotations, and is therefore aperiodic.
Alternately, a word is a Lyndon word if and only if it is nonempty and lexicographically strictly smaller than any of its proper suffixes, that is for all nonempty words such that and is nonempty.
Another characterisation is the following: A Lyndon word has the property that it is nonempty and, whenever it is split into two nonempty substrings, the left substring is always lexicographically less than the right substring. That is, if is a Lyndon word, and is any factorization into two substrings, with and understood to be non-empty, then . This definition implies that a string of length is a Lyndon word if and only if there exist Lyndon words and such that and . Although there may be more than one choice of and with this property, there is a particular choice, called the standard factorization, in which is as long as possible.
Enumeration
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 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ... 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 1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... Lyndon words correspond to aperiodic necklace class representatives and can thus be counted with Moreau's necklace-counting function.
Generation
provides an efficient algorithm for listing the Lyndon words of length at most with a given alphabet size in lexicographic order. If is one of the words in the sequence, then the next word after can be found by the following steps: Repeat the symbols from to form a new word of length exactly , where the th symbol of is the same as the symbol at position mod length() of . As long as the final symbol of is the last symbol in the sorted ordering of the alphabet, remove it, producing a shorter word. Replace the final remaining symbol of by its successor in the sorted ordering of the alphabet. The worst-case time to generate the successor of a word by this procedure is . However, if the words being generated are stored in an array of length , and the construction of from is performed by adding symbols onto the end of rather than by making a new copy of , then the average time to generate the successor of (assuming each word is equally likely) is constant. Therefore, the sequence of all Lyndon words of length at most can be generated in time proportional to the length of the sequence. 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 or words whose length divides , by filtering out the generated words that do not fit these criteria.
Standard factorization
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. The final Lyndon word in this sequence is the lexicographically smallest suffix of the given string. A factorization into a nonincreasing sequence of Lyndon words (the so-called Lyndon factorization) can be constructed in linear time. Lyndon factorizations may be used as part of a bijective variant of the Burrows–Wheeler transform for data compression, and in algorithms for digital geometry.