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.
A separation between RLSLPs and LZ77 / Bille, Philip; Gagie, Travis; Gørtz, Inge Li; Prezza, Nicola. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - 50:(2018), pp. 36-39. [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 non definito
Dimensione
96.31 kB
Formato
Adobe PDF
|
96.31 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Caricamento pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
