Линдон сөздері: лексикографиялық реттегі ең кіші тізбектер

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 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.

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 .

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. and in algorithms for digital geometry. 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. 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. Indeed, they provide an explicit construction for the commutators appearing in the Poincaré–Birkhoff–Witt theorem needed for the construction of universal enveloping algebras. Every Lyndon word can be understood as a permutation, the suffix standard permutation.

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. Lyndon words may be understood as a special case of Hall sets. 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.