A nonempty finite word that is strictly smaller in lexicographic order than each of its nontrivial cyclic rotations. For example, is a Lyndon word, whereas is not because its rotation is smaller.
A prefix of a word that is itself a Lyndon word. The longest Lyndon prefix is useful when ranking necklaces and substrings of a De Bruijn sequence.
Articles by others on the same topic
A **Lyndon word** is a non-empty string that is strictly smaller than all of its nontrivial suffixes in the lexicographical order. More formally, a string \( w \) is called a Lyndon word if it cannot be written as a nontrivial concatenation of two smaller strings, i.e.