Space-efficient conversions from SLPs

Given a straight-line program with $g$ rules for a text $T [1..n]$, we can build the $z$-phrase the LZ77 parse of $T$ in $O (g)$ space and either $n\,\mathrm{polylog} (n)$ time with high probability or $O (g z \log^2 n)$ time deterministically. We can also build a locally consistent grammar of optimal size $g' = O(\delta\log\frac{n}{\delta})$ in $O(n\log n)$ expected time and $O(g+g')$ space.