The smallest grammar problem revisited

Artur Jez; Carl Philipp Reh; Danny Hucke; Hideo Bannai; Markus Lohrey; Momoko Hirayama; Shunsuke Inenaga

The smallest grammar problem revisited

T0 review · 0 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper closes the approximation-ratio gaps for LZ78 and BISECTION.

desk verdict Tight bounds for LZ78 and BISECTION look right, but the RePair lower bound has a genuine gap: the proof bounds an intermediate grammar, not the final one. read the letter →

arxiv 1908.06428 v1 pith:MJYCRH4A submitted 2019-08-18 cs.DS

Hideo Bannai , Momoko Hirayama , Danny Hucke , Shunsuke Inenaga , Artur Jez , Markus Lohrey , Carl Philipp Reh This is my paper · ORCID

classification cs.DS

keywords stringcompressionsmallestgrammarproblemapproximationratioLZ78BISECTIONRePairstraight-lineprogramgrammar-based

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper settles, up to constant factors, how badly two classic grammar-based compressors can behave in the worst case. For a word, the approximation ratio is the size of the grammar the compressor outputs divided by the size of a smallest straight-line program (SLP) for that word, maximized over all words of length $n$. The paper proves LZ78's worst-case ratio is $\Theta((n/\log n)^{2/3})$ for every alphabet size $k$ with $2 \le k \le n$, and BISECTION's is $\Theta(\sqrt{n/\log n})$. It also raises the lower bound for RePair from $\Omega(\sqrt{\log n})$ to $\Omega(\log n/\log\log n)$ using binary words, and improves the alphabet-reduction result from a factor $24+\varepsilon$ to a factor $6$: a constant-factor approximation for binary strings would give a constant-factor approximation for arbitrary alphabets. These are among the first exact (up to constants) worst-case guarantees for practical grammar compressors, and the lower-bound word families live over binary alphabets.

What carries the argument

The proofs are carried by four explicit constructions and one translation. (1) For BISECTION, the hard word is $s_k = (u_k a^{m_k+1})^{m_k} u_k$, where $u_k$ concatenates the $k$ binary code words of length $\lceil\log k\rceil$ separated by runs $a^{m_k}$; any split into equal power-of-two blocks yields $\Omega(2^k)$ distinct factors, so BISECTION's SLP is large, while the word has an SLP of size $O(k)$. (2) For LZ78, the hard word is $s_{m,k}=a^{k(k+1)/2}b^{m(2m+1)}u_{m,k}v_{m,k}$ with $u_{m,k}=((a^k b^{2m+1}a)^m(a^k b^{m+1})^2)^k a^k$ and $v_{m,k}=(\prod_{i=1}^m b^i a^k)^{k^2}$; the unique LZ78 factorization is shown to produce $\Theta(k^2 m)$ distinct phrases. (3) For RePair, the hard word is $s_k=\prod_{i=1}^{k-1}(a\,w_k[1:k+i]\,b)\,a\,w_k$, where $w_k$ comes from a binary sequence of order $\lceil\log k\rceil$ in which each length-$\lceil\log k\rceil$ word occurs once, mapped by $0\mapsto 01$, $1\mapsto 10$; after $k-1$ rounds the start rule already contains $\Omega(k^2/\log k)$ distinct length-$\Theta(\log k)$ patterns, forcing a large grammar. (4) The alphabet reduction uses $\varphi(c_i)=a^i b$, with lemmas showing any SLP over the large alphabet becomes an SLP for the binary image with size at most $3|A|$, and any SLP for a binary image can be converted back with size at most $2|B|$, giving the factor $6c$.

What would settle it

Run the paper's exact RePair variant on the constructed binary words $s_k$ for increasing $k$, and compare the grammar size after $k-1$ rounds with the size after RePair reaches its final grammar. If the final grammar is ever $o(k^2/\log k)$—that is, if later rounds shrink the intermediate grammar enough to break the $\Omega(k^2/\log k)$ bound—then the claimed lower bound for RePair is false. The words and algorithm are specified explicitly, so this is a concrete finite test.

Watch

Extended reading notes

Core claim

The central discovery is that the gaps left by earlier analysis of the smallest grammar problem can be closed with explicit word families. For BISECTION, a family of binary words is constructed whose optimal grammar has size $O(k)$ while BISECTION must generate $\Omega(2^k)$ distinct nonterminals when splitting into power-of-two blocks; this yields ratio $\Omega(2^k/k)$, and since the word length is $n = \Theta(2^{2k}/k)$, ratio $\Omega(\sqrt{n/\log n})$. For LZ78, the word family $s_{m,k}$ forces $\Theta(k^2 m)$ distinct LZ78 factors while the optimal grammar has size $O(\log k + m)$; taking $m = \lceil\log k\rceil$ gives ratio $\Omega(k^2)$, and with $n = \Theta(k^3 \log k)$ this is $\Theta((n/\log n)^{2/3})$. For RePair, binary words built from a sequence in which every length-$\lceil\log k\rceil$ block occurs exactly once force any grammar for the intermediate start rule to have size $\Omega(k^2/\log k)$ while the whole word has an SLP of size $O(k)$, yielding $\Omega(\log n/\log\log n)$. Finally, the homomorphism $\varphi(c_i)=a^i b$ translates SLPs between arbitrary and binary alphabets with constant-factor size changes in both directions, improving the alphabet-reduction constant from $24+\varepsilon$ to $6$.

Load-bearing premise

The RePair lower-bound proof assumes that the grammar after the first $k-1$ replacement rounds is a lower bound on the size of RePair's final grammar; if later rounds can compress that intermediate grammar below $\Omega(k^2/\log k)$, the claimed lower bound does not follow.

Editorial extensions

If this is right

For every alphabet size $k$ with $2 \le k \le n$, no algorithm can improve LZ78's worst-case output beyond a constant factor of $(n/\log n)^{2/3}$ times the optimal grammar: the ratio is asymptotically tight.
BISECTION's worst-case output is asymptotically tight at $\Theta(\sqrt{n/\log n})$ times optimal, matching the earlier upper bound.
RePair's approximation ratio is at least $\Omega(\log n/\log\log n)$, so RePair cannot serve as the polynomial-time compressor with ratio $o(\log n/\log\log n)$ that would resolve the long-standing addition-chain problem.
A constant-factor approximation for binary strings would imply a factor-$6$ constant-factor approximation for arbitrary alphabets, improving the previous factor $24+\varepsilon$.
All lower bounds hold over binary alphabets, so the hardness is not an artifact of unbounded alphabets.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper establishes asymptotic $\Theta$ bounds but does not extract the hidden constants; computing them for the constructed families would show at which finite lengths the worst cases become visible, a natural next step the paper leaves open.
The BISECTION lower bound relies on the algorithm's fixed power-of-two splitting rule; a natural (untested) extension is that a variant splitting at the midpoint or at another balanced point might evade the $\Omega(\sqrt{n/\log n})$ ratio.
The alphabet-reduction constant $6$ is one factor away from $8569/8568$, the threshold that would transfer the known inapproximability of the smallest grammar problem to binary strings; optimizing the encoding further is a promising direction.
The technique of fully characterizing the LZ78 factorization of a crafted word may also yield exact ratios for variants such as LZW or for online dictionary compressors, though the paper does not analyze them.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this is a genuinely useful paper whose central LZ78 and BISECTION results I largely trust, but the RePair lower bound as written does not go through. The referee should not desk-reject it; they should send it back for a serious repair of Theorem 3.7.

What is new: exact Θ((n/log n)^{2/3}) for LZ78 and Θ(sqrt(n/log n)) for BISECTION, with binary-alphabet constructions; improved RePair lower bound; reduction factor 6 versus 24+ε. These are real advances over Charikar et al. The word families are intricate, and I don't see circularity or hidden parametric fitting. The LZ78 factorization analysis in Section 3.2 is painstaking and convincing; Claims 1 and 2 line up. Same for BISECTION: the F_k factor set argument is clean, n=Θ(2^{2k}/k), k=Θ(log n) gives the right exponent. If there is a flaw there, I don't see it.

Where the paper breaks: Theorem 3.7, Claim 2. The proof fixes G, the SLP after k−1 rounds, and argues that the start rule of G has many distinct factors of length Θ(log k), hence |RePair(s_k)| = Ω(k^2/log k). But RePair's total grammar size is non-increasing under replacement: replacing ℓ ≥ 2 by one nonterminal with r ≥ 2 occurrences changes size by ℓ − (ℓ−1)r ≤ 0. So G is an upper bound on the final size, not a lower bound. Later rounds could shrink the grammar substantially. The proof gives no argument that the later rounds only shave o(k^2/log k). This matters because the a-blocks have the doubling structure A_{i+1} ∈ {A_i A_i, A_i A_i a}, so after k−1 rounds there is still a lot of repeated structure across blocks, and RePair could plausibly collapse much of it. The theorem may be true—I suspect it is—but this proof doesn't establish it.

The rest of the paper holds up. Lemma 3.10 (binary decoding with the ψ-normal form) is intricate; I checked the size bound 2|B| and the confluence claim, and it looks right. The Arpe–Reischuk improvement to factor 6 is a nice, much simpler construction.

Who this is for: anyone working on grammar-based compression, approximation ratios of dictionary compressors, or LZ/RePair lower bounds. The LZ78 and BISECTION halves alone are worth publishing. The RePair half needs an additional idea. I'd send it to a serious referee with a request to focus on Theorem 3.7 and would expect a revised version or a separate corrected proof. Not desk material.

Referee Report

0 major / 6 minor

Summary. The paper studies the worst-case approximation ratio of grammar-based compressors, defined as |C(w)|/g(w), where g(w) is the size of a smallest straight-line program for w. It claims three main results: the approximation ratio of LZ78 is Θ((n/log n)^{2/3}) for every alphabet size k with 2 ≤ k ≤ n; the approximation ratio of BISECTION is Θ(√(n/log n)) for the same range; and the lower bound for RePair is improved from Ω(√log n) to Ω(log n/log log n). The paper also gives a simplification of an Arpe–Reischuk reduction, improving the constant from 24+ε to 6, and a minor result on the exact threshold length 2k²+2k+1 for when every word of length n over a k-letter alphabet has a nontrivial SLP. The proofs for LZ78 and BISECTION are based on explicit word families and use the upper bounds from Charikar et al. as black boxes; the RePair lower bound uses a De Bruijn sequence construction and claims a lower bound on the size of an intermediate grammar's start rule.

Significance. If the results hold, they are significant: they provide the first exact worst-case approximation ratios for two widely used grammar-based compressors, LZ78 and BISECTION, and they improve the known lower bound for RePair in a way that excludes RePair as a candidate for improving Yao's addition-chain method. The LZ78 and BISECTION analyses appear sound, with explicit, parameter-free word families and careful accounting of the factorization and SLP sizes. The binary-alphabet reduction is clean and improves a previously technical construction. The RePair proof is more delicate, but a careful reading shows that the contested final inference can be justified by a short argument that the final grammar, restricted to the nonterminals introduced after the first k−1 rounds, is an SLP for the intermediate start rule with the X_i treated as terminals. The manuscript would benefit from stating this argument explicitly.

minor comments (6)

[Theorem 3.7, Claim 2 (Section 3.3)] The final sentence of Claim 2, saying that the lower bound on a smallest SLP for the start rule of G implies |RePair(s_k)| = Ω(k²/log k), is too terse and can be misread as an invalid comparison with the intermediate grammar size. It is valid for the following reason: the final RePair grammar, after deleting the productions for X_1,...,X_{k−1} and treating those symbols as terminals, is an SLP for the start rule of G, so its size is at least g(start rule of G). Please add this justification explicitly; without it, the proof is easy to misunderstand.
[Example 3.5 (Section 3.2)] The example labeled u_{2,4}, v_{2,4}, and s_{2,4} actually instantiates the parameters k=4, m=2, not k=2, m=4. The strings shown are ((a⁴b⁵a)²(a⁴b³)²)⁴a⁴ and (ba⁴b²a⁴)¹⁶, which match the definition for k=4, m=2. Please rename the example to u_{4,2}, v_{4,2}, and s_{4,2}, or change the parameters consistently.
[Section 4] Section 4, titled 'Hardness of grammar-based compression for binary alphabets,' is empty in the submitted text. Either restore the intended content or remove the heading, and move the sentence 'The goal of this section is to prove the following result' before Theorem 3.8 to the appropriate location.
[References] Several references contain typos or LaTeX artifacts: reference [16] lists 'SPIRE 2017, volume 9954' but the year 2016 and volume correspond to SPIRE 2016; reference [6] contains 'Springer, 1996. to appear'; and references [13]–[15] contain 'Micha/suppress l' artifacts that should be cleaned up.
[Section 3.1, definition of m_k] The displayed definition of m_k has lost its braces: it should read m_k = 2^{k−⌈log k⌉} − ⌈log k⌉, not the ambiguous '2 k−⌈log2 k⌉ − ⌈log2 k⌉'.
[Proposition 2.2] The proof of Proposition 2.2 leaves the verification that the constructed word w_k is not in M_{3,2} ∪ M_{2,3} to 'one can check.' A short argument or a reference to a detailed example would make this minor result easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation; the lower bounds are proved from explicit word families and the upper bounds are external black boxes.

full rationale

No circular step is present. The lower bounds for BISECTION, LZ78, and RePair are obtained by constructing explicit word families (s_k, s_{m,k}, s_k respectively) and separately proving that (i) the compressor's output on those words is large and (ii) a smallest SLP is small. The small-SLP upper bounds use Lemma 2.1, whose ingredients are either proved in the paper or cited to external work (Berstel–Brlek [3] for point 1, Charikar et al. [7] for points 2, 3, and 5); none of those ingredients is the approximation-ratio statement being proved. The matching upper bounds for BISECTION and LZ78 are imported from Charikar et al. [7] as black boxes, and using an external upper bound to close a lower-bound gap is not circular. Theorem 3.8 is proved by the self-contained translation Lemmas 3.9 and 3.10. The only self-reference in the paper is the note that a short version appeared at SPIRE 2016 [16], which is not load-bearing. A separate, non-circular correctness concern: in Theorem 3.7, Claim 2, the proof bounds the start rule of the SLP G produced after k-1 RePair rounds and concludes 'therefore |RePair(s_k)| ∈ Ω(k²/log k)'; since RePair size is non-increasing under replacements, |G| is an upper bound, not a lower bound, on the final grammar size. This is an inference gap in the written proof, but it is a proof error rather than a circular definition, a fitted input renamed as a prediction, or a self-citation chain, so it does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted, hand-chosen, or ad-hoc numerical parameters; its constructions use integer variables k and m that are chosen in the proofs but not fitted to data. The central claims rest on standard prior results about SLPs and on the standard models of the three compressors. No new entities (forces, particles, conserved quantities) are postulated.

assumptions (4)

standard math Lemma 2.1 (known SLP properties): every word of length n has an SLP of size O(n/log_σ n); powers and concatenations can be represented with small overhead; a string contains at most g(w)*k distinct factors of length k.
Quoted from [3] and [7]; the paper relies on these bounds in all three lower-bound constructions.
standard math Berstel-Brlek theorem: g(σ,n) = Θ(n/log_σ n).
Used to bound the size of the smallest SLP for auxiliary words such as u'_k and to justify the general O(n/log n) benchmark.
standard math Existence and property of binary De Bruijn sequences of every order.
Used in Theorem 3.7 to build the word w_k with unique length-⌈log k⌉ factors.
domain assumption The algorithmic models of LZ78, BISECTION, and RePair as formalized in Charikar et al. [7].
The paper's approximation ratio definitions and the claim about BISECTION's behavior on equal-length blocks depend on these models.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The smallest grammar problem revisited." pith.science (2026). https://pith.science/paper/MJYCRH4A

@misc{pith2026190806428,
  author       = {Pith},
  title        = {Pith review of: The smallest grammar problem revisited},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MJYCRH4A}},
  note         = {Machine review of arXiv:1908.06428}
}

abstract

In a seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Here the gaps for $\mathsf{LZ78}$ and $\mathsf{BISECTION}$ are closed by showing that the approximation ratio of $\mathsf{LZ78}$ is $\Theta( (n/\log n)^{2/3})$, whereas the approximation ratio of $\mathsf{BISECTION}$ is $\Theta(\sqrt{n/\log n})$. In addition, the lower bound for $\mathsf{RePair}$ is improved from $\Omega(\sqrt{\log n})$ to $\Omega(\log n/\log\log n)$. Finally, results of Arpe and Reischuk relating grammar-based compression for arbitrary alphabets and binary alphabets are improved.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Re-Pair In Small Space
cs.DS 2019-08 reject novelty 7.0 of 10

A new algorithm computes Re-Pair, a grammar-based compression method, in O(n^2) time using roughly text-sized working space, but the core frequency-counting proof appears to overcount repeated-character bigrams.

Reference graph

Works this paper leans on

42 extracted references · 41 canonical work pages · cited by 1 Pith paper

[1]

Some theory and practice of greedy oﬀ-line textual substitution

Alberto Apostolico and Stefano Lonardi. Some theory and practice of greedy oﬀ-line textual substitution. In Proceedings of DCC 1998 , pages 119–128. IEEE Computer Society, 1998

work page 1998
[2]

On the complexity of opti mal grammar-based compres- sion

Jan Arpe and R¨ udiger Reischuk. On the complexity of opti mal grammar-based compres- sion. In Proceedings of Data Compression Conference (DCC 2006) , pages 173–182. IEEE Computer Society, 2006

work page 2006
[3]

On the length of word chain s

Jean Berstel and Srecko Brlek. On the length of word chain s. Inf. Process. Lett., 26(1):23–28, 1987

work page 1987
[4]

Space-eﬃ cient Re-Pair compression

Philip Bille, Inge Li Gørtz, and Nicola Prezza. Space-eﬃ cient Re-Pair compression. In Pro- ceedings of DCC 2017 , pages 171–180, 2017

work page 2017
[5]

Landau, Rajeev Raman, Kunihiko Sada kane, Srinivasa Rao Satti, and Oren Weimann

Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sada kane, Srinivasa Rao Satti, and Oren Weimann. Random access to grammar-compressed strings and trees. SIAM Journal on Computing, 44(3):513–539, 2015

work page 2015
[6]

Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin G ras, and Markus L. Schmid. On the complexity of grammar-based compression over ﬁxed alphabets. In Proceedings of ICALP 2016, Lecture Notes in Computer Science. Springer, 1996. to appe ar

work page 2016
[7]

Charikar, E

M. Charikar, E. Lehman, A. Lehman, D. Liu, R. Panigrahy, M . Prabhakaran, A. Sahai, and A. Shelat. The smallest grammar problem. IEEE Trans. Inf. Theory , 51(7):2554–2576, 2005

work page 2005
[8]

Fast and compact w eb graph representations

Francisco Claude and Gonzalo Navarro. Fast and compact w eb graph representations. ACM Transactions on the Web , 4(4):16:1–16:31, 2010

work page 2010

Show all 42 references

[9]

A combinatorial problem

Nicolaas de Bruijn. A combinatorial problem. Proc. Koninklijke Nederlandse Akademie v. Wetenschappen, pages 758–764, 1946

1946
[10]

A.A. Diwan. A new combinatorial complexity measure for languages. Tata Institute, Bombay, India, 1986

1986
[11]

Mr-repair: Grammar compression based on maxim al repeats

Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Takuya Kida. Mr-repair: Grammar compression based on maxim al repeats. In Proceedings of DCC 2019 , pages 508–517. IEEE, 2019

2019
[12]

Rpair: Rescaling RePair with Rsync

Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, and Yoshi- masa Takabatake. Rpair: Rescaling RePair with Rsync. CoRR, abs/1906.00809, 2019. URL: http://arxiv.org/abs/1906.00809

1906 arXiv
[13]

Entropy bounds for grammar compression

Micha/suppress l Ga´ nczorz. Entropy bounds for grammar compression. CoRR, abs/1804.08547, 2018. URL: http://arxiv.org/abs/1804.08547

2018 arXiv
[14]

Entropy lower bounds for dictionary compression

Micha/suppress l Ga´ nczorz. Entropy lower bounds for dictionary compression. In Proceedings of CPM 2019, volume 128 of LIPIcs, pages 11:1–11:18. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Infor- matik, 2019

2019
[15]

Improvements on Re-Pair grammar compressor

Micha/suppress l Ga´ nczorz and Artur Je˙ z. Improvements on Re-Pair grammar compressor. In Proceed- ings of DCC 2017 , pages 181–190. IEEE, 2017

2017
[16]

The sm allest grammar problem re- visited

Danny Hucke, Markus Lohrey, and Carl Philipp Reh. The sm allest grammar problem re- visited. In Proceedings of SPIRE 2017, volume 9954 of LNCS, pages 35–49, 2016. URL: https://doi.org/10.1007/978-3-319-46049-9_4

2017 doi
[17]

Approximation ratios of RePair, LongestM atch and Greedy on unary strings

Danny Hucke. Approximation ratios of RePair, LongestM atch and Greedy on unary strings. to appear in Proceedings of SPIRE 2019

2019
[18]

Approximation of grammar-based compressi on via recompression

Artur Je˙ z. Approximation of grammar-based compressi on via recompression. Theoretical Computer Science, 592:115–134, 2015

2015
[19]

A really simple approximation of smallest grammar

Artur Je˙ z. A really simple approximation of smallest grammar. Theoretical Computer Science, 616:141–150, 2016. 1The table on page 2556 in [7] states the better lower bound of 1 .37 . . ., but the authors only show the lower bound 1 .137 . . ., see [7, Theorem 11]. THE SMALLE...

2016
[20]

At the roots of dictionary compression: string attractors

Dominik Kempa and Nicola Prezza. At the roots of dictionary compression: string attractors. In Proceedings of STOC 2018 , pages 827–840. ACM, 2018

2018
[21]

J. C. Kieﬀer and E.-H. Yang. Grammar-based codes: A new c lass of universal lossless source codes. IEEE Trans. Inf. Theory , 46(3):737–754, 2000

2000
[22]

J. C. Kieﬀer, E.-H. Yang, G. J. Nelson, and P. C. Cosman. U niversal lossless compression via multilevel pattern matching. IEEE Trans. Inf. Theory , 46(4):1227–1245, 2000

2000
[23]

Kieﬀer, Philippe Flajolet, and En-Hui Yang

John C. Kieﬀer, Philippe Flajolet, and En-Hui Yang. Uni versal lossless data compression via binary decision diagrams. CoRR, abs/1111.1432, 2011. URL: http://arxiv.org/abs/1111.1432

2011 arXiv
[24]

Kieﬀer and En hui Yang

John C. Kieﬀer and En hui Yang. Structured grammar-base d codes for universal lossless data compression. Communications in Information and Systems , 2(1):29–52, 2002

2002
[25]

Rao Kosaraju and Giovanni Manzini

S. Rao Kosaraju and Giovanni Manzini. Compression of lo w entropy strings with Lempel-Ziv algorithms. SIAM Journal on Computing , 29(3):893–911, 1999

1999
[26]

N. J. Larsson and A. Moﬀat. Oﬄine dictionary-based compression. In Proc. DCC 1999, pages 296–305. IEEE, 1999

1999
[27]

Lohrey, S

M. Lohrey, S. Maneth, and R. Mennicke. XML tree structur e compression using RePair. Inform. Syst. , 38(8):1150–1167, 2013

2013
[28]

Algorithmics on SLP-compressed strings: A survey

Markus Lohrey. Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryp- tology, 4(2):241–299, 2012

2012
[29]

Online grammar transformation based on re-pair algorithm

Takuya Masaki and Takuya Kida. Online grammar transformation based on re-pair algorithm. In Proceedings of DCC 2016 , pages 349–358. IEEE, 2016

2016
[30]

Nevill-Manning and Ian H

Craig G. Nevill-Manning and Ian H. Witten. Identifying hierarchical strcture in sequences: A linear-time algorithm. J. Artif. Intell. Res. (JAIR) , 7:67–82, 1997

1997
[31]

Repair and all irredu cible grammars are upper bounded by high-order empirical entropy

Carlos Ochoa and Gonzalo Navarro. Repair and all irredu cible grammars are upper bounded by high-order empirical entropy. IEEE Transactions on Information Theory , 65(5):3160– 3164, 2019

2019
[32]

Experiments in text ﬁle compression

Frank Rubin. Experiments in text ﬁle compression. Commun. ACM , 19(11):617–623, 1976. URL: http://doi.acm.org/10.1145/360363.360368

1976
[33]

W. Rytter. Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. , 302(1–3):211–222, 2003

2003
[34]

A fully linear-time approximation a lgorithm for grammar-based compres- sion

Hiroshi Sakamoto. A fully linear-time approximation a lgorithm for grammar-based compres- sion. J. Discrete Algorithms , 3(2-4):416–430, 2005

2005
[35]

Storer and Thomas G

James A. Storer and Thomas G. Szymanski. Data compressi on via textual substitution. J. ACM, 29(4):928–951, 1982

1982
[36]

A succinct grammar compres- sion

Yasuo Tabei, Yoshimasa Takabatake, and Hiroshi Sakamo to. A succinct grammar compres- sion. In Proceedings of the 24th Annual Symposium on Combinatorial P attern Matching, CPM 2013 , volume 7922 of Lecture Notes in Computer Science , pages 235–246. Springer, 2013

2013
[37]

En-Hui Yang and John C. Kieﬀer. Eﬃcient universal lossl ess data compression algorithms based on a greedy sequential grammar transform - part one: Wi thout context models. IEEE Transactions on Information Theory , 46(3):755–777, 2000

2000
[38]

On the evaluation of powers

Andrew Chi-Chih Yao. On the evaluation of powers. SIAM Journal on Computing , 5(1):100– 103, 1976

1976
[39]

Compression of individua l sequences via variable-rate cod- ing

Jacob Ziv and Abraham Lempel. Compression of individua l sequences via variable-rate cod- ing. IEEE Transactions on Information Theory , 24(5):530–536, 1977

1977
[40]

R. Wan. Browsing and Searching Compressed Documents. P hD thesis, Dept. of Computer Science and Software Engineering, University of Melbourne , 2003

2003
[41]

T. Kida, T. Matsumoto, Y. Shibata, M. Takeda, A. Shinoha ra, and S. Arikawa. Collage sys- tems: a unifying framework for compressed pattern matching. Theoretical Computer Science, 298(1):253–272, 2003

2003
[42]

Gonz´ alez and G

R. Gonz´ alez and G. Navarro. Compressed text indexes with fast locate. In Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching, C PM 2007 , volume 4580 of Lecture Notes in Computer Science , pages 216—227. Springer, 2007. 20 H. BANNAI, M. HIRAYAMA, D. HU...

2007

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Some theory and practice of greedy oﬀ-line textual substitution

Alberto Apostolico and Stefano Lonardi. Some theory and practice of greedy oﬀ-line textual substitution. In Proceedings of DCC 1998 , pages 119–128. IEEE Computer Society, 1998

work page 1998

[2] [2]

On the complexity of opti mal grammar-based compres- sion

Jan Arpe and R¨ udiger Reischuk. On the complexity of opti mal grammar-based compres- sion. In Proceedings of Data Compression Conference (DCC 2006) , pages 173–182. IEEE Computer Society, 2006

work page 2006

[3] [3]

On the length of word chain s

Jean Berstel and Srecko Brlek. On the length of word chain s. Inf. Process. Lett., 26(1):23–28, 1987

work page 1987

[4] [4]

Space-eﬃ cient Re-Pair compression

Philip Bille, Inge Li Gørtz, and Nicola Prezza. Space-eﬃ cient Re-Pair compression. In Pro- ceedings of DCC 2017 , pages 171–180, 2017

work page 2017

[5] [5]

Landau, Rajeev Raman, Kunihiko Sada kane, Srinivasa Rao Satti, and Oren Weimann

Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sada kane, Srinivasa Rao Satti, and Oren Weimann. Random access to grammar-compressed strings and trees. SIAM Journal on Computing, 44(3):513–539, 2015

work page 2015

[6] [6]

Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin G ras, and Markus L. Schmid. On the complexity of grammar-based compression over ﬁxed alphabets. In Proceedings of ICALP 2016, Lecture Notes in Computer Science. Springer, 1996. to appe ar

work page 2016

[7] [7]

Charikar, E

M. Charikar, E. Lehman, A. Lehman, D. Liu, R. Panigrahy, M . Prabhakaran, A. Sahai, and A. Shelat. The smallest grammar problem. IEEE Trans. Inf. Theory , 51(7):2554–2576, 2005

work page 2005

[8] [8]

Fast and compact w eb graph representations

Francisco Claude and Gonzalo Navarro. Fast and compact w eb graph representations. ACM Transactions on the Web , 4(4):16:1–16:31, 2010

work page 2010