2017/03/17 by Danny Hucke, Artur Jeż, Hucke, Danny +3
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #E.4 #F.2.2 #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1703.06061
openalex publication_date 2017/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a seminal paper of Charikar et al.~on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors. Here we improve the lower bound for the famous \sf RePair algorithm from Ω(√(log n)) to Ω(log n/loglog n). The family of words used in our proof is defined over a binary alphabet, while the lower bound from Charikar et al. needs an alphabet of logarithmic size in the length of the provided words.