4 citations · 4 across the 3 of their papers we have counts for
13 papers
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…
Regular Languages in the Sliding Window Model
Moses Ganardi, Danny Hucke, Markus Lohrey +2
We study the space complexity of the following problem: For a fixed regular language , we receive a stream of symbols and want to test membership of a sliding window of size …
A Comparison of Empirical Tree Entropies
Danny Hucke, Markus Lohrey, Louisa Seelbach Benkner
Whereas for strings, higher-order empirical entropy is the standard entropy measure, several different notions of empirical entropy for trees have been proposed in the past, notabl…
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…
Randomized sliding window algorithms for regular languages
Moses Ganardi, Danny Hucke, Markus Lohrey
A sliding window algorithm receives a stream of symbols and has to output at each time instant a certain value which only depends on the last symbols. If the algorithm is rando…
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.…
Automata theory on sliding windows
Moses Ganardi, Danny Hucke, Daniel König +2
In a recent paper we analyzed the space complexity of streaming algorithms whose goal is to decide membership of a sliding window to a fixed language. For the class of regular lang…
Universal Tree Source Coding Using Grammar-Based Compression
Danny Hucke, Markus Lohrey
We apply so-called tree straight-line programs to the problem of lossless compression of binary trees. We derive upper bound on the maximal pointwise redundancy (or worst-case redu…
Circuit Evaluation for Finite Semirings
Moses Ganardi, Danny Hucke, Daniel König +1
The computational complexity of the circuit evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or multiplicative identity. T…
Tree compression using string grammars
Moses Ganardi, Danny Hucke, Markus Lohrey +1
We study the compressed representation of a ranked tree by a (string) straight-line program (SLP) for its preorder traversal, and compare it with the well-studied representation by…
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…