# Inverse Lyndon words and Inverse Lyndon factorizations of words

arXiv: https://arxiv.org/abs/1705.10277 · HTML: https://mlsanity.com/paper/1705.10277/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2017.

## Built on by (most cited first, 1 of 1)

- [Numeric Lyndon-based feature embedding of sequencing reads for machine learning approaches](https://mlsanity.com/paper/2202.13884/) (2022)

## Abstract (arXiv)

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.