|
Title |
Space-efficient Conversions from SLPs |
|
Authors |
Travis Gagie, Adrián Goga, Artur Jez, Gonzalo Navarro |
|
Publication date |
2024 |
|
Abstract |
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(d log (n/d)) from the SLP within O(g+g_lc) space and in O(n log g) time, where d 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. |
|
Pages |
146-161 (part I |
|
Conference name |
International Symposium of Latin American Theoretical Informatics |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
Reference URL |
|
