arXiv Open Access 2017

A Separation Between Run-Length SLPs and LZ77

Philip Bille Travis Gagie Inge Li Gørtz Nicola Prezza

Lihat Sumber

Abstrak

In this paper we give an infinite family of strings for which the length of the Lempel-Ziv'77 parse is a factor $Ω(\log n/\log\log n)$ smaller than the smallest run-length grammar.

Topik & Kata Kunci

cs.DS

Penulis (4)

Philip Bille

Travis Gagie

Inge Li Gørtz

Nicola Prezza

Format Sitasi

APA MLA BibTeX

Bille, P., Gagie, T., Gørtz, I.L., Prezza, N. (2017). A Separation Between Run-Length SLPs and LZ77. https://arxiv.org/abs/1711.07270

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓