## Bounds on two LZ78-style Grammars

### Golnaz Badkobeh

We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally produce a grammar for a string of length *n*; we show that the size of this grammar can be larger than the size of the smallest grammar by a factor *Ω(n^⅓)*. We also show that the standard algorithms using *Θ(z)* working space to construct the LZD and LZMW parsings, where *z* is the size of the parsing, work in
*Ω(n^*^{5}⁄_{4}) time in the worst case.