4 citations · 4 across the 2 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.DS2017★ 4 cited
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.…
cs.FL2017
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…
cs.IT2017
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…