Generalized Straight-Line Programs

It was recently proved that any Straight-Line Program (SLP) generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We generalize this proof to a general class of grammars we call Generalized SLPs (GSLPs), which allow rules of the form $A\to x$ where $x$ is any Turing-complete representation (of size $\mathrm{\mid }x\mathrm{\mid }$) of a sequence of symbols (potentially much longer than $\mathrm{\mid }x\mathrm{\mid }$). We then specialize GSLPs to so-called Iterated SLPs (ISLPs), which allow rules of the form $A\to {\mathrm{\Pi }}_{i=k_1}^{k_2}{B}_1^{i^{c_1}}\cdots B_t^{i^{c_t}}$ of size $2t+2$. We prove that ISLPs break, for some text families, the measure $\delta$ based on substring complexity, a lower bound for most measures and compressors exploiting repetitiveness. Further, ISLPs can extract any substring of length $\lambda$, from the represented text $T[\mathrm{1..}n]$, in time $O(\lambda +{\log }^{2}n\log \log n)$. This is the first compressed representation for repetitive texts breaking $\delta$ while, at the same time, supporting direct access to arbitrary text symbols in polylogarithmic time. We also show how to compute some substring queries, like range minima and next/previous smaller value, in time $O({\log }^{2}n\log \log n)$. Finally, we further specialize the grammars to Run-Length SLPs (RLSLPs), which restrict the rules allowed by ISLPs to the form $A\to B^t$. Apart from inheriting all the previous results with the term ${\log }^{2}n\log \log n$ reduced to the near-optimal $\log n$, we show that RLSLPs can exploit balance to efficiently compute a wide class of substring queries we call ``composable’’ – i.e., $f(X\cdot Y)$ can be obtained from $f(X)$ and $f(Y)$…