Abstract

We explore an extension to straight-line programs (SLPs) that outperforms, for some text families, the measure ? based on substring complexity, a lower bound for most measures and compressors exploiting repetitiveness (which are crucial in areas like Bioinformatics). The extension, called iterated SLPs (ISLPs), allows rules of the form A??i=k1k2B1ic1?Btict, for which we show how to extract any substring of length ?, from the represented text T[1..n], in time O(?+log2nloglogn). This is the first compressed representation for repetitive texts breaking ? while, at the same time, supporting direct access to arbitrary text symbols in polylogarithmic time. As a byproduct, we extend Ganardi et al.’s technique to balance any SLP (so it has a derivation tree of logarithmic height) to a wide generalization of SLPs, including ISLPs. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.