39 citations · 255 across the 76 of their papers we have counts for
Showing 2009Show all
3 papers · 1 filter
cs.DS2009
Grammar-Based Compression in a Streaming Model
Travis Gagie, Pawel Gawrychowski
We show that, given a string of length , with constant memory and logarithmic passes over a constant number of streams we can build a context-free grammar that generates …
cs.DS2009★ 4 cited
Minimax Trees in Linear Time
Pawel Gawrychowski, Travis Gagie
A minimax tree is similar to a Huffman tree except that, instead of minimizing the weighted average of the leaves' depths, it minimizes the maximum of any leaf's weight plus its de…
cs.DS2009
Online validation of the pi and pi' failure functions
Pawel Gawrychowski, Artur Jez, Lukasz Jez
Let pi_w denote the failure function of the Morris-Pratt algorithm for a word w. In this paper we study the following problem: given an integer array A[1..n], is there a word w ove…