###
Balancing Run-Length Straight-Line Programs

####
Gonzalo Navarro, Francisco Olivares, and Cristian Urbina

It was recently proved that any SLP generating a given string *w* can be
transformed in linear time into an equivalent balanced SLP of the same
asymptotic size. We show that this result also holds for RLSLPs, which are
SLPs extended with run-length rules of the form *A --> B^t* for
*t > 2*, deriving *exp(A) = exp(B)^t*. An immediate consequence is the
simplification of the algorithm for extracting substrings of an
RLSLP-compressed string. We also show that several problems like answering
RMQs and computing Karp-Rabin fingerprints on substrings can be solved in
*O(grl)* space and *O(log n)* time, *grl* being the size of
the smallest RLSLP generating the string, of length *n*. We extend the
result to solving more general operations on string ranges, in
*O(grl)*
space and *O(log n)* applications of the operation. In general, the
smallest RLSLP can be asymptotically smaller than the smallest SLP by up to an
*O(log n)* factor, so our results can make a difference in terms of the space needed for computing these operations efficiently for some string families.