arXiv preprint ·
The Inverse Lyndon Array
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Lyndon array stores, at each position of a word, the length of the longest Lyndon factor starting at that position and plays an important role in combinatorics on words, for example, in the construction of fundamental data structures such as the suffix array. In this paper, we introduce the Inverse Lyndon array, the analogous structure for inverse Lyndon words, namely words that are lexicographically greater than all their proper nonempty suffixes. Unlike standard Lyndon words, inverse Lyndon words may have non-trivial borders, which introduces a genuine theoretical difficulty. We show that the Inverse Lyndon array can be characterized in terms of the next greater suffix array together with a border-correction term, and we prove that this correction coincides with a longest common extension (LCE) value. Building on this characterization, we adapt the nearest-suffix framework underlying Ellert's linear-time construction of the Lyndon array to the inverse setting, obtaining an O(n)-time algorithm for general ordered alphabets. Finally, we show that the Inverse Lyndon array can also be used to reconstruct the canonical inverse Lyndon factorization in linear time.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Testing and Learning Symbolic Finite State Machines
Contributions to the hierarchy of probabilistic languages
Learning Shuffle Ideals with Membership Queries and Contrastive Examples
Fast and Robust Temporal Logic Planning via ADMM-based Trajectory Optimization
Constraints Are Graphs, Not Chains: Exact Decoding for Diffusion Language Models
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.