1 citations · 1 across the 1 of their papers we have counts for
3 papers
cs.DS2019
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,…
cs.DS2018
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…
cs.DS2017★ 1 cited
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…