## 1 Introduction  
The smallest grammar problem--namely, finding a smallest context-free grammar that generates exactly one sequence--is of practical and theoretical importance in fields such as Kolmogorov complexity, data compression and pattern discovery. The size of a smallest grammar can be considered a computable variant of Kolmogorov complexity, in which the Turing machine description of the sequence is restricted to context-free grammars. The problem is then decidable, but still hard: the problem of finding a smallest grammar with an approximation ratio smaller than \(\frac{8569}{8568}\) is NP-HARD [1]. Nevertheless, a \(\mathcal{O}(\log^{3}n)\) approximation ratio--with \(n\) the length of the sequence--can be achieved by a simple algorithmic scheme based on an approximation to the shortest superstring problem [1] and a smaller \(\mathcal{O}(\log n/g)\) (where \(g\) is the size of a smallest grammar) approximation ratio is possible through more complex mappings from the LZ77-factorization of the sequence to a context-free grammar with a balanced parsing tree [1,2]. If the grammar is small, storing the grammar instead of the sequence can be interesting from a data compression perspective. [PERSON] and [PERSON] developed the formal framework of compression by _Grammar Based Codes_ from the viewpoint of information theory, defining irreducible grammars and demonstrating their universality [3]. Before this formalization, several algorithms allowing to compress a sequence by context-free grammars had already been proposed. The LZ78-factorization introduced by [PERSON] and [PERSON] in [4] can be interpreted as a context-free grammar. Let us remark that this is not true for LZ77, published one year before [5]. Moreover, it is a commonly used result that the size of a LZ77-factorization is a lower bound on the size of a smallest grammar [1,2]. The first approach that generated explicitly a context-free grammar with compression ability is _Sequitur_[6]. Like LZ77 and LZ78, Sequitur is an on-line algorithm that processes the sequence from left to right. It incrementally maintains a grammar generating the part of the sequence read, introducing and deleting production to ensure that no digram (pair of adjacent symbols) occurs more than once and that each rule is used at least twice. Other algorithms consider the entire sequence before choosing which repeated substring will be rewritten by the introduction of a new rule. Most of these offline algorithms proceed in a greedy manner, selecting in each iteration one repeated word \(w\) according to a score function and replacing all the (non-overlapping) occurrences of the repeat \(w\) in the whole grammar by a new terminal \(N\) and adding the new production \(N\to w\) to the grammar. Different heuristics have been used to choose the repeat: the most frequent one [7], the longest [8] and the one that reduces the most the size of the resulting grammar (Compressive[9]). Greedy[10] belongs to this last family but the score used for choosing the words is oriented toward directly optimizing the number of bits needed to encode the grammar rather than minimizing its size. The running time of Sequitur is linear and linear-time implementations of the first two algorithms exists: RePair[11] and Longest First[12], while the existence of a linear-time algorithm for Compressive and Greedy remains an open question. In pattern discovery, a smallest grammar is a good candidate for being the one that generates the data according to Occam's razor principle. In that case, the grammar may not only be used for compressing the sequence but also to unveil its structure. Inference of the hierarchical structure of sequences was the initial motivation of Sequitur and has been the subject of several papers applying this scheme to DNA sequences [6,13,14], musical scores [15] or natural languages [7,16]. It can also be a first step to learn more general grammars along the lines of [17].