arXiv preprint ·
A Factor-5 Conversion to Internal Collage Systems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
A collage system is a grammar-based compression model that extends straight-line programs with repetition and substring truncation. Internal collage systems additionally require every nonterminal to be structurally reachable from the start symbol. Migita, Uehata, and I (CPM 2026) showed that any collage system of size $m$ can be converted into an internal one generating the same string with size at most $9m$, and left the improvement of this constant as an open problem. We show that a simple refinement of their top-down conversion reduces the bound to $5m$. The proof combines three elementary ideas: canonicalization of generated truncations that remain aligned with a target endpoint; a repetition decomposition that absorbs every complete copy of the repetition base into a maximal core; and monotonicity of structural reachability, which prevents an input truncation rule from both becoming structurally reachable and later acting as a hidden target at which endpoint alignment is lost. The conversion runs in deterministic $O(m^2)$ worst-case time in the stated unit-cost random-access machine model. Consequently, for every string, the minimum size of an internal collage system is at most five times the minimum size of a general collage system.
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
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.