4 citations · 4 across the 3 of their papers we have counts for
6 papers · 1 filter
A Non-constant Lower Bound for Grammar-Based Compression with Greedy
Danny Hucke
We prove a lower bound of Ω(log n/ log log n) on the approximation ratio of the global grammar-based compression algorithm Greedy. To our knowledge, the previously best lower bound…
Sliding window property testing for regular languages
Moses Ganardi, Danny Hucke, Markus Lohrey +1
We study the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the…
The smallest grammar problem revisited
Hideo Bannai, Momoko Hirayama, Danny Hucke +4
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,…
Entropy Bounds for Grammar-Based Tree Compressors
Danny Hucke, Markus Lohrey, Louisa Seelbach Benkner
The definition of -order empirical entropy of strings is extended to node labelled binary trees. A suitable binary encoding of tree straight-line programs (that have been u…
Approximation ratio of RePair
Danny Hucke, Artur Jez, Markus Lohrey
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.…
Constructing small tree grammars and small circuits for formulas
Moses Ganardi, Danny Hucke, Artur Jez +2
It is shown that every tree of size over a fixed set of different ranked symbols can be decomposed (in linear time as well as in logspace) into $O\big(\frac{n}{\log_σn}\big…