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.
Bille, Philip; Gagie, Travis; Gørtz, Inge Li; Prezza, Nicola. (2018). A separation between RLSLPs and LZ77. JOURNAL OF DISCRETE ALGORITHMS, (ISSN: 1570-8667), 50: 36-39. Doi: 10.1016/j.jda.2018.09.002.
A separation between RLSLPs and LZ77
Prezza, Nicola
2018
Abstract
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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
separation.pdf
Open Access
Tipologia:
Documento in Pre-print
Licenza:
DRM (Digital rights management) non definiti
Dimensione
96.31 kB
Formato
Adobe PDF
|
96.31 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
