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 N + (n + n') (n+σ) + 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, σ is the alphabet size, n is the number of variables in G and n' ≤ n is the number of symmetric centroid paths in the DAG representation for G.
No takes yet. Share an insight, caveat, or question.
Takasaka et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: