Space-efficient SLP Encoding for $O(\log N)$-time Random Access
<|reference_start|>Space-efficient SLP Encoding for $O(\log N)$-time Random Access: A Straight-Line Program (SLP) $G$ for a string $T$ is a context-free grammar (CFG) that derives $T$ only, which can be considered as a compressed representation of $T$. In this paper, we show how to encode $G$ in $n \lceil \lg N \rceil + (n + n') \lceil \lg (n+\sigma) \rceil + 4n - 2n' + o(n)$ bits to support random access queries of extracting $T[p..q]$ in worst-case $O(\log N + p - q)$ time, where $N$ is the length of $T$, $\sigma$ is the alphabet size, $n$ is the number of variables in $G$ and $n' \le n$ is the number of symmetric centroid paths in the DAG representation for $G$.<|reference_end|>
@article{takasaka2024space-efficient,
    title={Space-efficient SLP Encoding for $O(\log N)$-time Random Access},
    author={Akito Takasaka and Tomohiro I},
    journal={arXiv preprint arXiv:2406.15011},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.15011},
    primaryClass={cs.DS}
}