Paperlane

no. 5 · Friday 30 October 2026

Logarithmic Separation between LZ77 and LZ-End and Grammar Compression

Philip Bille, Inge Li Gørtz, Rikke Jessen, Jingxun Li, Simon Rumle Tarnow and Renfei Zhou

math.IT · v2

Abstract

We show that there is a logarithmic separation between LZ77 and LZ-End, and between LZ77 and grammar compression.

fields
Information Theory
pdf ↗ page arXiv:2610.32818 ↗