English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

It was recently proved that any SLP generating a given string $w$ can betransformed in linear time into an equivalent balanced SLP of the sameasymptotic size. We show that this result also holds for RLSLPs, which are SLPsextended with run-length rules of the form $A \rightarrow B^t$ for $t>2$,deriving $\texttt{exp}(A) = \texttt{exp}(B)^t$. An immediate consequence is thesimplification of the algorithm for extracting substrings of anRLSLP-compressed string. We also show that several problems like answering RMQsand computing Karp-Rabin fingerprints on substrings can be solved in$\mathcal{O}(g_{rl})$ space and $\mathcal{O}(\log n)$ time, $g_{rl}$ being thesize of the smallest RLSLP generating the string, of length $n$. We extend theresult to solving more general operations on string ranges, in$\mathcal{O}(g_{rl})$ space and $\mathcal{O}(\log n)$ applications of theoperation. In general, the smallest RLSLP can be asymptotically smaller thanthe smallest SLP by up to an $\mathcal{O}(\log n)$ factor, so our results canmake a difference in terms of the space needed for computing these operationsefficiently for some string families.

Balancing Run-Length Straight-Line Programs*