A separation between RLSLPs and LZ77

Research output: Research - peer-reviewJournal article – Annual report year: 2018

View graph of relations

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 Ω(logn/loglogn)-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 Ω(logn/loglogn)-factor separation between RLSLPs and LZ77.
Original languageEnglish
JournalJournal of Discrete Algorithms
Number of pages9
ISSN1570-8667
DOIs
StateAccepted/In press - 2018
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

  • Grammar-based compression, Run-length compression, SLP, RLSLP, LZ77, Thue-Morse sequence
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 158485987