On the complexity and approximability of Bounded access Lempel Ziv coding

Ferdinando Cicalese, Francesca Ugazio

We study the complexity of constructing an optimal parsing $\phi$ of a string $\mathbf{s}=s_1\dots s_n$ under the constraint that given a position $p$ in the original text, and the LZ…