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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Grammar compression is a general compression framework in which a string $T$of length $N$ is represented as a context-free grammar of size $n$ whoselanguage contains only $T$. In this paper, we focus on studying the limitationsof algorithms and data structures operating on strings in grammar-compressedform. Previous work focused on proving lower bounds for grammars constructedusing algorithms that achieve the approximation ratio$\rho=\mathcal{O}(\text{polylog }N)$. Unfortunately, for the majority ofgrammar compressors, $\rho$ is either unknown or satisfies$\rho=\omega(\text{polylog }N)$. In their seminal paper, Charikar et al. [IEEETrans. Inf. Theory 2005] studied seven popular grammar compression algorithms:RePair, Greedy, LongestMatch, Sequential, Bisection, LZ78, and$\alpha$-Balanced. Only one of them ($\alpha$-Balanced) is known to achieve$\rho=\mathcal{O}(\text{polylog }N)$.  We develop the first technique for proving lower bounds for data structuresand algorithms on grammars that is fully general and does not depend on theapproximation ratio $\rho$ of the used grammar compressor. Using thistechnique, we first prove that $\Omega(\log N/\log \log N)$ time is requiredfor random access on RePair, Greedy, LongestMatch, Sequential, and Bisection,while $\Omega(\log\log N)$ time is required for random access to LZ78. Allthese lower bounds hold within space $\mathcal{O}(n\text{ polylog }N)$ andmatch the existing upper bounds. We also generalize this technique to proveseveral conditional lower bounds for compressed computation. For example, weprove that unless the Combinatorial $k$-Clique Conjecture fails, there is nocombinatorial algorithm for CFG parsing on Bisection (for which it holds$\rho=\tilde{\Theta}(N^{1/2})$) that runs in $\mathcal{O}(n^c\cdotN^{3-\epsilon})$ time for all constants $c>0$ and $\epsilon>0$. Previously,this was known only for $c<2\epsilon$.

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data