14 citations · 74 across the 41 of their papers we have counts for
14 papers · 1 filter
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,…
Balancing Straight-Line Programs
Moses Ganardi, Artur Jeż, Markus Lohrey
It is shown that a context-free grammar of size that produces a single string (such a grammar is also called a string straight-line program) can be transformed in linear ti…
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…
Grammar-based Compression of Unranked Trees
Adrià Gascón, Markus Lohrey, Sebastian Maneth +2
We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and g…
Optimal top dag compression
Markus Lohrey, Carl Philipp Reh, Kurt Sieber
It is shown that for a given ordered node-labelled tree of size and with many different node labels, one can construct in linear time a top dag of height and si…