  Motivated by applications to string processing, we introduce variants of the
Lyndon factorization called inverse Lyndon factorizations. Their factors, named
inverse Lyndon words, are in a class that strictly contains anti-Lyndon words,
that is Lyndon words with respect to the inverse lexicographic order. The
Lyndon factorization of a nonempty word w is unique but w may have several
inverse Lyndon factorizations. We prove that any nonempty word w admits a
canonical inverse Lyndon factorization, named ICFL(w), that maintains the main
properties of the Lyndon factorization of w: it can be computed in linear time,
it is uniquely determined, it preserves a compatibility property for sorting
suffixes. In particular, the compatibility property of ICFL(w) is a consequence
of another result: any factor in ICFL(w) is a concatenation of consecutive
factors of the Lyndon factorization of w with respect to the inverse
lexicographic order.
