## 6 Non-Uniqueness of Smallest Grammar and Structure Discovery
### Bounds on the Number of Smallest Grammars  
It is clear that a smallest grammar is not necessarily unique. Not so clear is how many smallest grammars there can be. First we will prove that for a certain family of sequences, any node of the search space corresponds to a smallest grammar. As in the proof of Proposition 1 and only to ease the understanding of the proof, we will use \(|G|=\sum_{A\rightarrow\alpha\in\mathcal{P}}(|\alpha|)\) as the definition of grammar size. **Proposition 2**. : _Let \(m(k)=\max_{s\colon|s|=n}(\text{number of global minima for }\langle\mathcal{R}(s),\subseteq\rangle)\)._  
_Then, \(m(n)\in\Omega(c^{n})\), with \(c>1\) constant._  
**Proof. ** It is sufficient to find one family of sequences for which the number of global minima is exponential. Consider the sequence  
\[s_{k}=a_{1}a_{1}|_{1}a_{1}a_{1}|_{2}a_{2}a_{2}|_{1}a_{2}a_{2}|_{2}\ldots|_{2}a _{k}a_{k}|_{1}a_{k}a_{k}|_{2}=\prod_{i=1}^{k}(a_{i}a_{i}|_{1}a_{i}a_{i}|_{2})\]  
of length \(n=6k\) over an alphabet of size \(k+2\). The \(a_{i}\)'s are single symbols. The set of repeated substrings longer than one is \(\{a_{i}a_{i},1\leq i\leq k\}\), of size \(k\). For any subset, there is only one minimal grammar with this constituent set. Adding any remaining constituents to this grammar reduces the length of the axiom rule by 2, but does not reduce anything in the remaining rules, and adds 2 to the grammar size. The same happens when a constituent is removed. Therefore, any node of the lattice is a local minimum, and therefore a global. As there are \(2^{\frac{n}{6}}\) nodes, this proves the proposition. \begin{table}
\begin{tabular}{l||c c c c c||c c c|c} \hline  & \multicolumn{4}{c||}{**Algorithms from the literature**} & \multicolumn{4}{c|}{**Optimizing occurrences**} \\ \hline  & & & \multicolumn{3}{c||}{IRR} & \multicolumn{3}{c|}{IRRCOO} & \multicolumn{1}{c}{} \\ Sequences & Sequitur & LZ78 & MF & ML & MC & MF & ML & MC & ZZ \\ \hline alice29.txt & 49,147 & 116,296 & 42,453 & 56,056 & **41,000** & 39,794 & 52,351 & **39,251** & **37,701** \\ avgoulik.txt & 44,123 & 102,296 & 38,507 & 51,470 & **37,474** & 36,822 & 48,133 & **36,384** & **35,000** \\ ep.html & 9,835 & 22,658 & 8,479 & 9,612 & **8,048** & 8,369 & 9,313 & **7,941** & **7,767** \\ fields.c & 4,108 & 11,056 & 3,765 & 3,980 & **3,416** & 3,713 & 3,892 & **3,373** & **3,311** \\ grammar.lsp & 1,770 & 4,225 & 1,615 & 1,730 & **1,473** & 1,621 & 1,704 & **1,471** & **1,465** \\ kennedy.sls & 174,585 & 365,466 & 167,076 & 179,753 & **166,924** & 166,817 & 179,281 & **166,760** & **166,704** \\ ket10.txt & 112,205 & 288,250 & 92,913 & 130,409 & **90,099** & 90,493 & 120,140 & **88,561** & – \\ plrabn12.txt & 142,656 & 338,762 & 125,366 & 180,203 & **124,198** & **114,959** & 164,728 & 117,326 & – \\ pt5 & 55,692 & 106,456 & 45,639 & 56,452 & **45,135** & 44,192 & 53,738 & **43,958** & – \\ sum & 15,329 & 35,056 & 12,965 & 13,866 & **12,207** & 12,878 & 13,695 & **12,114** & **12,027** \\ xargs.1 & 2,329 & 5,309 & 2,137 & 2,254 & **2,006** & 2,142 & 2,237 & **1,989** & **1,972** \\ \hline \end{tabular}
\end{table} 
Table 2: Grammar sizes on the Canterbury corpus. The files over which [PERSON] did not finished are marked with a dash. Now, we will suppose that the set of constituents is fixed and consider the number of smallest grammars that can be built with this set. Given a set of constituents \(Q\) we denote with [PERSON]mathcal{G}_{Q}\) the set of all the smallest grammars that can be formed with \(Q\). Different implementations of the _mgp_ algorithm may return different grammars from \(\mathcal{G}_{Q}\). As the following Proposition shows, there are cases where the number of different smallest grammars can grow exponentially for a given set of constituents. **Proposition 3**. : _Let \(m(n)=\max\limits_{s\in\Sigma^{k},Q\subseteq repeats(s)}(|G_{Q\cup\{s\}}|)\)._  
_Then \(m(n)\in\Omega(c^{n})\), with \(c>1\) constant._  
**Proof. ** Let \(s_{k}\) be the following sequence \((aba)^{k}\) and let \(Q\) be \(\{ab,ba\}\).