A Separation Between Run-Length SLPs and LZ77
classification
💻 cs.DS
keywords
run-lengthfactorfamilygivegrammarinfinitelempel-zivlength
read the original abstract
In this paper we give an infinite family of strings for which the length of the Lempel-Ziv'77 parse is a factor $\Omega(\log n/\log\log n)$ smaller than the smallest run-length grammar.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.