Metraipolis › archive › dc_90535ece2705

A Non-constant Lower Bound for Grammar-Based Compression with Greedy — arXiv:2609.12106

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12106
License (as archived)
CC0-1.0
Archived
2026-10-16T03:58:59.459Z
SHA-256 of the archived text
6aa77fc6899b4fffb9a51493233c904117570c0a0e79b077ec1ed55d4599bb52
Stable URL of this page
https://metraipolis.com/documento/dc_90535ece2705

How to cite

A Non-constant Lower Bound for Grammar-Based Compression with Greedy — arXiv:2609.12106 — arXiv (en), https://arxiv.org/abs/2609.12106 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_90535ece2705 (Metraipolis archive dc_90535ece2705, sha256 6aa77fc6899b4fffb9a51493233c904117570c0a0e79b077ec1ed55d4599bb52)
BibTeX
@misc{dc90535ece2705,
  title = {A Non-constant Lower Bound for Grammar-Based Compression with Greedy — arXiv:2609.12106},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12106},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_90535ece2705; sha256 6aa77fc6899b4fffb9a51493233c904117570c0a0e79b077ec1ed55d4599bb52},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12106. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We prove a lower bound of {\Omega}(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound was a constant, and the existence of a nonconstant lower bound had remained open for more than twenty years. Our bound holds on an infinite family of words of length n, over alphabets of growing size, for every execution using left-to-right occurrence replacement and arbitrary tie-breaking. The lower bound is also formally verified in Lean 4.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-14 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Formal Languages and Automata Theory (cs.FL).
Pagina del lavoro: https://arxiv.org/abs/2609.12106 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:50:18.679Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).