On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression
Abstract
We introduce and study the adaptive covering complexity C adapt S (s), defined as the minimum number of contiguous factor blocks required to partition a string s when each block is either a factor of a fixed external dictionary S or a factor of the target's already decoded prefix. This hybrid admissibility model formalizes the structural interaction between static dictionary matching and dynamic nonoverlapping self-referencing. Our main theoretical result is the exact logarithmic law which is tight and proves that dynamic self-reference can reduce phrase count by at most an exponential factor over static dictionary covering alone. We establish structural equivalences showing that the measure bridges word-segmented Relative Lempel-Ziv and non-overlapping LZ77, and we prove exact preset-history LZ77 sandwich bounds. Furthermore, we establish the optimality of the longest-match greedy parse via an exchange lemma and present an optimal implementation based on dual suffix automata running in O(M + n) time and space for a constant alphabet. These analytical results are complemented by counting bounds, stationary-ergodic asymptotic invariance, a dictionaryselection NP-hardness result, and a concise empirical illustration.
Related
- Global smooth behavior in Kuznetsov and Westervelt type viscous wave equations: A unifying approach covering W1,q-small initial data
- The complexity of computing the covering radius of a Euclidean lattice
- Additive diameters and covering complexity of irreducible representations
- Unifying Data-Adaptive Longitudinal Treatment-Effect Subgroup Discovery and Pretreatment Membership Prediction
- Convolution Quadrature with Adaptive History Compression for Variable-Order Fractional Reaction--Diffusion Equations
BibTeX
@misc{marteau2026adaptive,
title = {{On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression}},
author = {Pierre-Fran\c cois Marteau},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26021},
eprint = {2610.26021},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26021},
}
RIS
TY - UNPB
TI - On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression
AU - Pierre-Fran{\c c}ois Marteau
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26021
UR - https://arxiv.org/abs/2610.26021
AB - We introduce and study the adaptive covering complexity C adapt S (s), defined as the minimum number of contiguous factor blocks required to partition a string s when each block is either a factor of a fixed external dictionary S or a factor of the target's already decoded prefix. This hybrid admissibility model formalizes the structural interaction between static dictionary matching and dynamic nonoverlapping self-referencing. Our main theoretical result is the exact logarithmic law which is tight and proves that dynamic self-reference can reduce phrase count by at most an exponential factor over static dictionary covering alone. We establish structural equivalences showing that the measure bridges word-segmented Relative Lempel-Ziv and non-overlapping LZ77, and we prove exact preset-history LZ77 sandwich bounds. Furthermore, we establish the optimality of the longest-match greedy parse via an exchange lemma and present an optimal implementation based on dual suffix automata running in O(M + n) time and space for a constant alphabet. These analytical results are complemented by counting bounds, stationary-ergodic asymptotic invariance, a dictionaryselection NP-hardness result, and a concise empirical illustration.
ER -