Space-Efficient Conversions from SLPs

We give algorithms that, given a straight-line program (SLP) with g rules that generates (only) a text T[1..n], build within O(g) space the Lempel-Ziv (LZ) parse of T (of z phrases) in time \(O(n\log ^2 n)\) or in time \(O(gz\log ^2(n/z))\) . We also show how to build a locally consistent grammar (LCG) of optimal size \(g_{lc} = O(\delta \log \frac{n}{\delta })\) from the SLP within \(O(g+g_{lc})\) space and in \(O(n\log g)\) time, where \(\delta \) is the substring complexity measure of T. Finally, we show how to build the LZ parse of T from such an LCG within \(O(g_{lc})\) space and in time \(O(z\log ^2 n \log ^2(n/z))\) . All our results hold with high probability.