2026-09-27T04:28:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25957 2026-09-23T23:56:59Z ddc:004 open_access

On the Smallest Size of Internal Collage Systems Migita, Soichiro Uehata, Kyotaro I, Tomohiro Collage Systems Dictionary-based compression Compressibility measures A Straight-Line Program (SLP) for a string T is a context-free grammar in Chomsky normal form that derives T only, which can be seen as a compressed form of T. Kida et al. introduced collage systems [Theor. Comput. Sci., 2003] to generalize SLPs by adding repetition rules and truncation rules. The smallest size c(T) of collage systems for T has gained attention to see how these generalized rules improve the compression ability of SLPs. Navarro et al. [IEEE Trans. Inf. Theory, 2021] showed that c(T) ∈ O(z(T)) and there is a string family with c(T) ∈ Ω(b(T) log |T|), where z(T) is the number of phrases in the Lempel-Ziv parsing of T and b(T) is the smallest size of bidirectional schemes for T. They also introduced a subclass of collage systems, called internal collage systems, and proved that its smallest size ĉ(T) for T is at least b(T). While c(T) ≤ ĉ(T) is obvious, it is unknown how large ĉ(T) is compared to c(T). In this paper, we prove that ĉ(T) = Θ(c(T)) by showing that any collage system of size m can be transformed into an internal collage system of size O(m) in O(m²) time. Thanks to this result, we can focus on internal collage systems to study the asymptotic behavior of c(T), which helps to suppress excess use of truncation rules. As a direct application, we get b(T) = O(c(T)), which answers an open question posed in [Navarro et al., IEEE Trans. Inf. Theory, 2021]. We also give a MAX-SAT formulation to compute ĉ(T) for a given T. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Soichiro Migita and Kyotaro Uehata and Tomohiro I 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.31 urn:nbn:de:0030-drops-259575 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.31 eng https://creativecommons.org/licenses/by/4.0/legalcode