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 k {\displaystyle k} -ary Lyndon word of length n > 0 {\displaystyle n>0} is an n {\displaystyle n} -character string over an alphabet of size k {\displaystyle k} which is the unique lexicographicallying minimal word in the multiset of all its rotations. In particular, a Lyndon word differs from all of its non-trivial rotations, so it is aperiodic by definition. Alternately, w {\displaystyle w} is a Lyndon word if and only if it is nonempty and lexicographically smaller than any of its proper suffixes: that is, for every factorization w = u v {\displaystyle w=uv} with u , v {\displaystyle u,v} nonempty words, we have w < v {\displaystyle w<v} (or equivalently, u < v {\displaystyle u<v} ). A recursive characterisation of Lyndon words is: w {\displaystyle w} is a single letter, or w = u v {\displaystyle w=uv} for smaller Lyndon words u , v {\displaystyle u,v} with u < v {\displaystyle u<v} . Although there may be more than one choice of such u , v {\displaystyle u,v} , there is a particular standard factorization in which v {\displaystyle v} 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, ... (sequence A001037 in the OEIS) Lyndon words correspond to aperiodic necklace class representatives and can thus be counted with Moreau's necklace-counting polynomial M n ( k ) {\displaystyle M_{n}(k)} .
Generation Duval (1988) provides an efficient algorithm for listing the Lyndon words of length at most n {\displaystyle n} with a given alphabet size s {\displaystyle s} in lexicographic order. If w {\displaystyle w} is one of the words in the sequence, then the next word after w {\displaystyle w} can be found by the following steps:
Repeat w {\displaystyle w} and truncate it to a new word x {\displaystyle x} of length exactly n {\displaystyle n} . As long as the final symbol of x {\displaystyle x} is the last symbol in the sorted ordering of the alphabet, remove it, producing a shorter word. Replace the final remaining symbol of x {\displaystyle x} by its successor in the sorted ordering of the alphabet. For example, suppose we are generating the binary Lyndon words of length up to 7, and we have generated up to w = 00111 {\displaystyle w=00111} , then the steps are:
Repeat and truncate to get x = 00111 00 111 {\displaystyle x=00111\;00{\cancel {111}}}
… excerpt ends here. Continue reading the full article.
