Lyndon words with a fixed standard right factor
Frédérique Bassino, Julien Clément, Cyril Nicaud · HAL (Le Centre pour la Communication Scientifique Directe) · 2004
Given a totally ordered alphabet A, a Lyndon word is a word that is strictly smaller, for the lexicographical order, than any of its conjugates (i.e., all words obtained by a circular permutation on the letters). Lyndon words were introduced by Lyndon [6] under the name of “standard lexicographic sequences ” in order to give a base for the free Lie algebra over A. The set of Lyndon words is denoted by L. For instance, with a binary alphabet A = {a, b}, the first Lyndon words until length five are L = {a, b,ab, aab, abb, aaab, aabb, abbb, aaaab, aaabb, aabab, aabbb, ababb, abbbb,...}. Note that a non-empty word is a Lyndon word if and only if it is strictly smaller than any of its proper suffixes. The standard (suffix) factorization of Lyndon words plays a central role in this framework (see [5], [7], [8]). For w ∈ L \\ A a Lyndon word not reduced to a letter, the pair (u, v) of Lyndon words such that w = uv and v of maximal length is called the standard factorization. The words u and v are called the left factor and right factor of the standard factorization. Equivalently, the right factor v of the standard factorization of a Lyndon word w which is not reduced to a letter can be defined as the smallest proper suffix of w for the lexicographical order. For instance we have the following standard factorizations: aaabaab = aaab · aab aaababb = a · aababb aabaabb = aab · aabb. One can then associate to a Lyndon word w a binary tree T(w) called its Lyndon tree recursively built in the following way: – if w is a letter, then T(w) is a leaf labeled by w, – otherwise T(w) is an internal node having T(u) and T(v) as children where u · v is the standard factorization of w.