Lyndon words are strings that are strictly smaller (lexicographically) than all of their proper suffixes. They are the “atoms” of lexicographic ordering — every string has a unique factorization into non-increasing Lyndon words. The Lyndon array of a string records, for each position, the length of the longest Lyndon factor starting there.
Negri et al. (arXiv:2603.17537) define and construct the inverse Lyndon array. Where the Lyndon array records factors that are smaller than all proper suffixes, the inverse Lyndon array records factors that are larger — anti-Lyndon words, strings that are lexicographically greater than every proper suffix starting within them.
Note (2026-11-12; read against the paper's full text): the paper cites earlier work on inverse Lyndon words and on an inverse canonical Lyndon factorization, including a border property for it, so the objects were already named; what it introduces is the inverse Lyndon array and its linear-time construction. The paper puts the difficulty in the fact that inverse Lyndon words may have non-trivial borders, unlike standard Lyndon words, which is why the array needs a border-correction term that it shows equals a longest common extension value; the essay does not mention borders. The paper adapts Ellert's linear-time construction and reports experiments on random, structured and real data. I found no mention of free Lie algebras, necklaces or de Bruijn sequences in the paper, so the remarks about the algebraic richness of Lyndon words and what the inverse objects do or do not inherit are the essay's.
The characterization is clean. The inverse Lyndon array can be expressed in terms of the next-greater-suffix array (which records where the next lexicographically larger suffix starts) plus a correction term equal to a longest common extension value. The relationship makes the structure computable in O(n) time — linear in the string length.
The construction is not a trivial mirror of the Lyndon case. Lyndon words have a rich theory connecting them to free Lie algebras, necklace enumeration, and de Bruijn sequences. The inverse objects don't inherit this algebraic richness directly, but they complete a symmetry: if you can decompose strings by their smallest factors, you should also be able to decompose them by their largest. The inverse array fills this gap.
Linear time is the standard for string algorithms — anything more is considered wasteful for a problem on sequences. The O(n) construction confirms that inverse Lyndon structure is computationally as natural as the forward version, despite being conceptually newer. The structure was always in the string; it just hadn't been named.