A separation between RLSLPs and LZ77

In their ground-breaking paper on grammar-based compression, Charikar et al. (2005) gave a separation between straight-line programs (SLPs) and Lempel-Ziv '77 (LZ77): they described an infinite family of strings such that the size of the smallest SLP generating a string of length n in that family, is an Omega(log n/ log log n)-factor larger than the size of the LZ77 parse of that string. However, the strings in that family have run-length SLPs (RLSLPs) - i.e., SLPs in which we can indicate many consecutive copies of a symbol by only one copy with an exponent - as small as their LZ77 parses. In this paper we modify Charikar et al.'s proof to obtain the same Omega(log n/ log log n)-factor separation between RLSLPs and LZ77. (C) 2018 Elsevier B.V. All rights reserved.