View source for Lyndon word

{{Short description|String that is strictly smaller in lexicographic order than all of its rotations}}
In [[mathematics]], in the areas of [[combinatorics]] and [[computer science]], a '''Lyndon word''' is a nonempty [[String (computer science)|string]] that is strictly smaller in [[lexicographic order]] than all of its [[Circular shift|rotations]]. Lyndon words are named after mathematician [[Roger Lyndon]], who investigated them in 1954, calling them '''standard lexicographic sequences'''.<ref>{{harvtxt|Lyndon|1954}}.</ref> [[Anatoly Shirshov]] introduced Lyndon words in 1953 calling them '''regular words'''.<ref>{{harvtxt|Shirshov|1953}}.</ref>  Lyndon words are a special case of [[Hall word]]s; almost all properties of Lyndon words are shared by Hall words.

==Definitions==
Several equivalent definitions exist.

A <math>k</math>-ary Lyndon word of length <math>n > 0</math> is an <math>n</math>-character [[String (computer science)#Formal theory|string]] over an [[Alphabet (computer science)|alphabet]] of size <math>k</math>, and which is the unique minimum element in the [[lexicographical order]]ing 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.<ref name="bpm">{{harvtxt|Berstel|Perrin|2007}}; {{harvtxt|Melançon|2001}}.</ref>

Alternately, a word <math>w</math> is a Lyndon word if and only if it is nonempty and lexicographically strictly smaller than any of its proper suffixes, that is <math>w < v</math> for all nonempty words <math>v</math> such that <math>w=uv</math> and <math>u</math> 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 <math>w</math> is a Lyndon word, and <math>w=uv</math> is any factorization into two substrings, with <math>u</math> and <math>v</math> understood to be non-empty, then <math>u < v</math>. This definition implies that a string <math>w</math> of length <math>\ge 2</math> is a Lyndon word if and only if there exist Lyndon words <math>u</math> and <math>v</math> such that <math>u < v</math> and <math>w=uv</math>.<ref name="m01" /> Although there may be more than one choice of <math>u</math> and <math>v</math> with this property, there is a particular choice, called the ''standard  factorization'', in which <math>v</math> is as long as possible.<ref name="bp07">{{harvtxt|Berstel|Perrin|2007}}.</ref>

==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, ... {{OEIS|A001037}}
Lyndon words correspond to aperiodic [[necklace (combinatorics)|necklace]] class representatives and can thus be counted with [[Moreau's necklace-counting function]].<ref name="bpm"/><ref>{{harvtxt|Ruskey|2003}} provides details of these counts for Lyndon words and several related concepts.</ref>

==Generation==
{{harvtxt|Duval|1988}} provides an efficient [[algorithm]] for listing the Lyndon words of length at most <math>n</math> with a given alphabet size <math>s</math> in [[lexicographic order]]. If <math>w</math> is one of the words in the sequence, then the next word after <math>w</math> can be found by the following steps:
#Repeat <math>w</math> and truncate it to a new word <math>x</math> of length exactly <math>n</math>.
#As long as the final symbol of <math>x</math> is the last symbol in the sorted ordering of the alphabet, remove it, producing a shorter word.
#Replace the final remaining symbol of <math>x</math> by its successor in the sorted ordering of the alphabet.
For example, suppose we have generated the binary Lyndon words of length up to 7, and we have generated up to <math>w = 00111</math>, then the steps are:

# Repeat and truncate to get <math>x = 00111\;00\cancel{111} </math>
# Since the last symbol is 0, it is not the final symbol.
# Increment the last symbol to obtain <math>x = 00111\;01 </math>.

The worst-case time to generate the successor of a word <math>w</math> by this procedure is <math>O(n)</math>.
However, if the words being generated are stored in an [[Array data structure|array]] of length <math>n</math>, and the construction of <math>x</math> from <math>w</math> is performed by adding symbols onto the end of <math>w</math> rather than by making a new copy of <math>w</math>, then the average time to generate the successor of <math>w</math> (assuming each word is equally likely) is constant. Therefore, the sequence of all Lyndon words of length at most <math>n</math> can be generated in time proportional to the length of the sequence.<ref>{{harvtxt|Berstel|Pocchiola|1994}}.</ref> A constant fraction of the words in this sequence have length exactly <math>n</math>, so the same procedure can be used to efficiently generate words of length exactly <math>n</math> or words whose length divides <math>n</math>, 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.<ref>{{harvtxt|Melançon|2001}}. {{harvtxt|Berstel|Perrin|2007}} write that although this is commonly credited to {{harvtxt|Chen|Fox|Lyndon|1958}}, and follows from results in that paper, it was not stated explicitly until {{harvtxt|Schützenberger|1965}}. It was formulated explicitly by {{harvtxt|Shirshov|1958}}, see {{harvtxt|Schützenberger|Sherman|1963}}.</ref> The final Lyndon word in this sequence is the lexicographically smallest suffix of the given string.<ref name="D83">{{harvtxt|Duval|1983}}.</ref> A factorization into a nonincreasing sequence of Lyndon words (the so-called Lyndon factorization) can be constructed in [[linear time]].<ref name="D83"/> Lyndon factorizations may be used as part of a bijective variant of the [[Burrows–Wheeler transform]] for [[data compression]],<ref>{{harvtxt|Gil|Scott|2009}}; {{harvtxt|Kufleitner|2009}}.</ref> and in algorithms for [[digital geometry]].<ref>{{harvtxt|Brlek|Lachaud|Provençal|Reutenauer|2009}}.</ref>

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.{{sfnp|Glen|2012}}
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 word|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.<ref>{{harvtxt|Melançon|1992}}; {{harvtxt|Melançon|Reutenauer|1989}}; {{harvtxt|Hohlweg|Reutenauer|2003}}</ref>
Indeed, they provide an explicit construction for the commutators appearing in the [[Poincaré–Birkhoff–Witt theorem]] needed for the construction of [[universal enveloping algebra]]s.

Every Lyndon word can be understood as a [[permutation]], the '''suffix standard permutation'''.

===Duval algorithm===
{{harvtxt|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. The resulting list of strings is the standard factorization of the given string. More formal description of the algorithm follows.

Given a string ''S'' of length ''N'', one should proceed with the following steps:
#Let ''m'' be the index of the symbol-candidate to be appended to the already collected symbols. Initially, ''m'' = 1 (indices of symbols in a string start from zero).
#Let ''k'' be the index of the symbol we would compare others to. Initially, ''k'' = 0.
#While ''k'' and ''m'' are less than ''N'', compare ''S''[''k''] (the ''k''-th symbol of the string ''S'') to ''S''[''m'']. There are three possible outcomes:
##''S''[''k''] is equal to ''S''[''m'']: append ''S''[''m''] to the current collected symbols. Increment ''k'' and ''m''.
##''S''[''k''] is less than ''S''[''m'']: if we append ''S''[''m''] to the current collected symbols, we'll get a Lyndon word. But we can't add it to the result list yet because it may be just a part of a larger Lyndon word. Thus, just increment ''m'' and set ''k'' to 0 so the next symbol would be compared to the first one in the string.
##''S''[''k''] is greater than ''S''[''m'']: if we append ''S''[''m''] to the current collected symbols, it will be neither a Lyndon word nor a possible beginning of one. Thus, add the first ''m''&minus;''k'' collected symbols to the result list, remove them from the string, set ''m'' to 1 and ''k'' to 0 so that they point to the second and the first symbol of the string respectively.
#When ''m'' > ''N'', it is essentially the same as encountering minus infinity, thus, add the first ''m''&minus;''k'' collected symbols to the result list after removing them from the string, set ''m'' to 1 and ''k'' to 0, and return to the previous step.
#Add ''S'' to the result list.

==Connection to de Bruijn sequences==
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
: 0  0001  0011  01  0111  1
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 [[L (complexity)|logarithmic space]].<ref>According to {{harvtxt|Berstel|Perrin|2007}}, the sequence generated in this way was first described (with a different generation method) by {{harvtxt|Martin|1934}}, and the connection between it and Lyndon words was observed by {{harvtxt|Fredricksen|Maiorana|1978}}.</ref>

==Additional properties and applications==
Lyndon words have an application to the description of [[free Lie algebra]]s, in constructing a basis for the homogeneous part of a given degree; this was Lyndon's original motivation for introducing these words.<ref name="m01">{{harvtxt|Melançon|2001}}.</ref> Lyndon words may be understood as a special case of [[Hall set]]s.<ref name="m01"/>

For prime ''p'', the number of irreducible [[monic polynomial]]s of degree ''d'' over the field <math>\mathbb{F}_p</math> 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.{{sfnp|Golomb|1969}}

A theorem of Radford states that a [[shuffle algebra]] over a field of characteristic 0 can be viewed as a polynomial algebra over the Lyndon words. More precisely, let ''A'' be an alphabet, let ''k'' be a field of characteristic 0 (or, more general, a commutative {{mathbb|Q}}-algebra), and let ''R'' be the free noncommutative ''k''-algebra {{math|''k'' ⟨ ''x<sub>a</sub>'' {{!}} ''a'' ∈ ''A'' ⟩}}. The words over ''A'' can then be identified with the "noncommutative monomials" (i.e., products of the ''x<sub>a</sub>'') in ''R''; namely, we identify a word (''a''<sub>1</sub>,''a''<sub>2</sub>,...,''a<sub>n</sub>'') with the monomial ''x''<sub>''a''<sub>1</sub></sub>''x''<sub>''a''<sub>2</sub></sub>...''x<sub>a<sub>n</sub></sub>''. 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
:1 ш ''v'' = ''v'' {{px2}} for any word ''v'';
:''u'' ш 1 = ''u'' {{px2}} for any word ''u'';
:''ua'' ш ''vb'' = (''u'' ш ''vb'')''a'' + (''ua'' ш ''v'')''b'' {{px2}} for any {{math|''a'',''b'' ∈ A}} and any words ''u'' and ''v''.
The ''shuffle algebra'' on the alphabet ''A'' is defined to be the additive group ''R'' endowed with ш as multiplication. Radford's theorem<ref name="radf79">{{harvtxt|Radford|1979}}</ref> 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.<ref name="radf79"/>

==See also==
* [[Lexicographically minimal string rotation]]
* [[Morphic word]]
* [[Sturmian word]]
* [[Necklace (combinatorics)]]

==Notes==
{{reflist|colwidth=30em}}

==References==
{{sfn whitelist|CITEREFMelançon2001}}
{{refbegin|colwidth=30em}}
*{{citation
 | last1 = Berstel | first1 = Jean
 | last2 = Perrin | first2 = Dominique | authorlink2 = Dominique Perrin 
 | doi = 10.1016/j.ejc.2005.07.019 | doi-access = free
 | mr = 2300777
 | issue = 3
 | journal = [[European Journal of Combinatorics]]
 | pages = 996–1022
 | title = The origins of combinatorics on words
 | url = http://www-igm.univ-mlv.fr/~berstel/Articles/2007Origins.pdf
 | volume = 28
 | year = 2007}}.
*{{citation
 | last1 = Berstel | first1 = J.
 | last2 = Pocchiola | first2 = M.
 | doi = 10.1016/0304-3975(94)00013-1
 | issue = 1–2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 1290554
 | pages = 415–425
 | title = Average cost of Duval's algorithm for generating Lyndon words
 | url = http://www-igm.univ-mlv.fr/~berstel/Articles/1994AverageCostDuval.pdf
 | volume = 132
 | year = 1994| doi-access = free
 }}.
*{{citation
 | last1 = Brlek | first1 = S.
 | last2 = Lachaud | first2 = J.-O.
 | last3 = Provençal | first3 = X.
 | last4 = Reutenauer | first4 = C.
 | doi = 10.1016/j.patcog.2008.11.010
 | issue = 10
 | journal = Pattern Recognition
 | pages = 2239–2246
 | title = Lyndon + Christoffel = digitally convex
 | url = http://www.lama.univ-savoie.fr/~provencal/articles/BrlekLachaudProvencalReutenauer--LyndonChristoffelConvex.pdf
 | volume = 42
 | year = 2009| bibcode = 2009PatRe..42.2239B
 }}.
*{{citation
 | last1 = Chen | first1 = K.-T.
 | last2 = Fox | first2 = R. H. | author2-link = Ralph Fox
 | last3 = Lyndon | first3 = R. C. | author3-link = Roger Lyndon
 | mr = 0102539
 | journal = [[Annals of Mathematics]] | series = 2nd Ser.
 | pages = 81–95
 | title = Free differential calculus. IV. The quotient groups of the lower central series
 | volume = 68
 | year = 1958
 | doi = 10.2307/1970044
 | issue = 1| jstor = 1970044
 }}.
*{{citation
 | last = Duval | first = Jean-Pierre
 | doi = 10.1016/0196-6774(83)90017-2
 | issue = 4
 | journal = Journal of Algorithms
 | pages = 363–381
 | title = Factorizing words over an ordered alphabet
 | volume = 4
 | year = 1983}}.
*{{citation
 | last = Duval | first = Jean-Pierre
 | doi = 10.1016/0304-3975(88)90113-2
 | mr = 979464
 | issue = 3
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | language = French
 | pages = 255–283
 | title = Génération d'une section des classes de conjugaison et arbre des mots de Lyndon de longueur bornée
 | volume = 60
 | year = 1988| doi-access = 
 }}.
*{{citation
 | last1 = Fredricksen | first1 = Harold
 | last2 = Maiorana | first2 = James
 | doi = 10.1016/0012-365X(78)90002-X
 | mr = 523071
 | issue = 3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 207–210
 | title = Necklaces of beads in ''k'' colors and ''k''-ary de Bruijn sequences
 | volume = 23
 | year = 1978| doi-access = free
 }}.
*{{citation
 | last1 = Gil | first1 = J.
 | last2 = Scott | first2 = D. A.
 | title = A bijective string sorting transform
 | url = http://bijective.dogma.net/00yyy.pdf
 | year = 2009}}.
*{{citation |first=Amy |last=Glen |title=Combinatorics of Lyndon Words |date=2012 |work=Mini-Conference: Combinatorics, representations, and structure of Lie type |publisher=University of Melbourne |url=https://amyglen.files.wordpress.com/2012/03/melbourne_talk_feb2012.pdf}}
*{{citation |author-link=Solomon W. Golomb |first=Solomon W. |last=Golomb |year=1969 |chapter=Irreducible polynomials, synchronizing codes, primitive necklaces and cyclotomic algebra |title=Combinatorial mathematics and its applications: Proceedings of the conference held at the University of North Carolina at Chapel Hill, April 10-14, 1967 |pages=358–370 |publisher=University of North Carolina Press |isbn=9780807878200 |series=University of North Carolina monograph series in probability and statistics |volume=4 |oclc=941682678  |editor-first=R.C. |editor-last=Bose |editor2-first=T.A. |editor2-last=Dowling}}
*{{citation |first1=Christophe |last1=Hohlweg |first2=Christophe |last2=Reutenauer |title=Lyndon words, permutations and trees |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |volume=307 |issue=1 |pages=173–8 |date=2003 |doi=10.1016/S0304-3975(03)00099-9 |url=https://www.lacim.uqam.ca/~christo/Publiés/2003/LyndonPermPreprint.pdf}}
*{{citation
 | last = Kufleitner | first = Manfred
 | editor1-last = Holub | editor1-first = Jan
 | editor2-last = Žďárek | editor2-first = Jan
 | contribution = On bijective variants of the [[Burrows-Wheeler transform]]
 | pages = 65–69
 | title = Prague Stringology Conference
 | url = http://www.stringology.org/event/2009/p07.html
 | year = 2009| bibcode = 2009arXiv0908.0239K |arxiv=0908.0239}}.
*{{Citation | last1=Lothaire | first1=M. | title=Combinatorics on words | url=https://books.google.com/books?id=UV9_3plEr8wC | publisher=Addison-Wesley Publishing Co., Reading, Mass. | series=Encyclopedia of Mathematics and its Applications | isbn=978-0-201-13516-9 | mr=675953 | year=1983 | volume=17}}
*{{citation
 | last = Lyndon | first = R. C. | authorlink = Roger Lyndon
 | mr = 0064049
 | journal = [[Transactions of the American Mathematical Society]]
 | pages = 202–215
 | title = On Burnside's problem
 | volume = 77
 | issue = 2 | year = 1954
 | doi=10.2307/1990868| jstor = 1990868 }}.
*{{citation
 | last = Martin | first = M. H.
 | doi = 10.1090/S0002-9904-1934-05988-3
 | mr = 1562989
 | issue = 12
 | journal = [[Bulletin of the American Mathematical Society]]
 | pages = 859–864
 | title = A problem in arrangements
 | volume = 40
 | year = 1934| doi-access = free
 }}.
*{{citation |first=Guy |last=Melançon |title=Combinatorics of Hall trees and Hall words |journal=[[Journal of Combinatorial Theory]] | series=Series A |volume=59 |issue=2 |pages=285–308 |date=1992 |doi=10.1016/0097-3165(92)90070-B|doi-access=free|url=https://core.ac.uk/download/pdf/82581798.pdf}}
*{{springer|id=l/l110200|last = Melançon | first = G.|title=Lyndon word}}
*{{citation |first1=Guy |last1=Melançon |first2=Christophe |last2=Reutenauer |title=Lyndon words, free algebras and shuffles |journal=Canadian Journal of Mathematics |volume=41 |issue=4 |pages=577–591 |date=1989 |doi=10.4153/CJM-1989-025-2 |s2cid=17395250 |url=|doi-access=free }}
*{{citation|last=Ruskey|first=Frank|year=2003|url=http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html|title=Info on necklaces, Lyndon words, De Bruijn sequences|url-status=dead|archiveurl=https://web.archive.org/web/20061002130346/http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html|archivedate=2006-10-02}}.
*{{citation
 | last1 = Schützenberger | first1 = M. P. | authorlink1=Marcel-Paul Schützenberger
 | last2 = Sherman | first2 = S
 | mr = 0158002
 | journal = Journal of Mathematical Analysis and Applications
 | pages = 482–488
 | title = On a formal product over the conjugate classes in a free group
 | volume = 7
 | issue = 3
 | year = 1963| doi = 10.1016/0022-247X(63)90070-2
 | doi-access = free
 }}.
*{{citation
 | last = Schützenberger | first = M. P. | authorlink=Marcel-Paul Schützenberger
 | mr = 0170971
 | journal = [[Proceedings of the American Mathematical Society]]
 | pages = 21–24
 | title = On a factorisation of free monoids
 | volume = 16
 | issue = 1
 | year = 1965
 | doi=10.2307/2033993| jstor = 2033993
 }}.
*{{citation 
 | last1=Shirshov | first1=A. I. | title=Subalgebras of free Lie algebras | mr=0059892 | year=1953 | journal=Mat. Sbornik |series=New Series | volume=33 | issue = 75  | pages=441–452}}
*{{citation 
 | last1=Shirshov
 | first1=A. I.
 | title=On free Lie rings
 | mr=0099356
 | year=1958
 | journal=Mat. Sbornik |series=New Series
 | volume=45
 | issue = 87
 | pages=113–122}}
*{{citation
 | last = Radford | first = David E.
 | journal = [[Journal of Algebra]]
 | pages = 432–454
 | title = A natural ring basis for the shuffle algebra and an application to group schemes
 | volume = 58
 | issue = 2
 | year = 1979
 | doi=10.1016/0021-8693(79)90171-6| doi-access = free
 }}.
{{refend}}

[[Category:Combinatorics on words]]