Two decades ago, a breakthrough in indexing string collections made it possible to
represent them within their compressed space while at the same time offering indexed …

Indexing highly repetitive texts—such as genomic databases, software repositories and
versioned text collections—has become an important problem since the turn of the …

While the th order empirical entropy is an accepted measure of the compressibility of
individual sequences on classical text collections, it is useful only for small values of and …

The size b of the smallest bidirectional macro scheme, which is arguably the most general
copy-paste scheme to generate a given sequence, is considered to be the strictest …

We explore an extension to straight-line programs (SLPs) that outperforms, for some text
families, the measure δ based on substring complexity, a lower bound for most measures …

Morphisms are widely studied combinatorial objects that can be used for generating infinite
families of words. In the context of Information theory, injective morphisms are called …

We introduce height-bounded LZ encodings (LZHB), a new family of compressed
representations that is a variant of Lempel-Ziv parsings with a focus on allowing fast access …

Repetitiveness measures reveal profound characteristics of datasets, and give rise to
compressed data structures and algorithms working in compressed space. Alas, the …

On the Hardness of Smallest RLSLPs and Collage Systems Page 1 On the Hardness of
Smallest RLSLPs and Collage Systems Akiyoshi Kawamoto†, Tomohiro I†, Dominik Köppl∗,+ …

Lossless data compression has been widely studied in computer science. One of the most
widely used lossless data compressions is Lempel-Ziv (LZ) 77 parsing, which achieves a …