# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 3 Upper Bound for Greedy
This means that for all \(Y\in M\) and \((Y\to v)\in P_{i}\), the length of the maximal \(X_{t}\)-block that occurs in \(v\) is strictly larger than the length of the maximal \(X_{t}\)-block that occurs in \(\gamma\). If \(t=k\), it follows that \(X_{k}\gamma\) is a factor of \(v\) for all \(Y\in M\) and \((Y\to v)\in P_{i}\), and symmetrically, if \(t=j\) then \(\gamma X_{j}\) is a factor of \(v\) for all \(Y\in M\) and \((Y\to v)\in P_{i}\). This contradicts the property that no strictly longer string than \(\gamma\) occurs at least as often on the right-hand sides of the rules. It follows that in this case \(\#_{i+1}(X_{t})\leq\#_{i}(X_{t})\), which finishes the proof. Lemma 5: _If a unary nonterminal \(X\) is introduced in some round \(i+1\) and \(X\to Z^{d}\) with \(d\geq 2\) is the corresponding rule, then \(\#_{i+1}(X)\leq\#_{i}(Z)\) and \(\#_{i+1}(Z)\leq\#_{i}(Z)+1\)._  
Proof. : Both points are straightforward: A rule \((Y\to v)\in P_{i+1}\) only contains \(X\) on the right-hand side if \(Z^{d}\) is a factor of \(v^{\prime}\) for \((Y\to v^{\prime})\in P_{i}\), which shows that \(\#_{i+1}(X)\leq\#_{i}(Z)\). For the second point, note that if \((Y\to v)\in P_{i}\) does not contain \(Z\) on the right-hand side, then the same is true for (the unchanged rule) \((Y\to v)\in P_{i+1}\). The only rule where \(Z\) occurs new is the new rule \(X\to Z^{d}\), and thus \(\#_{i+1}(Z)\leq\#_{i}(Z)+1\). So far, we have shown that when a unary nonterminal \(X\) is introduced and \(X\to Z^{d}\) with \(d\geq 2\) is the corresponding rule, then \(Z\) is a unary nonterminal as well (Corollary 1). Furthermore, we argued that introducing a nonunary nonterminal does not increase the number of rules where a unary nonterminal occurs on the right-hand side (Lemma 4). It follows that we can upper-bound the number of unary nonterminals and the number of rules where those nonterminals occur on right-hand sides independently of the nonunary nonterminals. To do so, we inductively define a binary tree \(T_{i}\) that describes how the unary nonterminals evolve until \(\mathbb{A}_{i}\) is reached. All nodes in the tree are labeled with \((X,k)\), where \(X\) is a unary nonterminal and \(k\) is an upper bound on \(\#_{j}(X)\) for some \(j\). 1. Initially, the tree \(T_{0}\) only contains a single node that is labeled with \((X_{0},1)\). 2. If a rule \(X\to Z^{d}\) is introduced in round \(i+1\) for some \(d\geq 2\), then we update \(T_{i}\) to \(T_{i+1}\) by adding two children to the unique leaf that is labeled with \((Z,k)\) for some \(k\). The new left child is labeled with \((Z,k+1)\) and the new right child is labeled with \((X,k)\) as depicted on the left of Figure 1.
3. If otherwise a nonunary nonterminal is introduced in round \(i+1\), then \(T_{i+1}=T_{i}\), i.e., nonunary nonterminals are ignored. The initial tree \(T_{0}\) reflects that the only unary nonterminal of \(\mathbb{A}_{0}\) is \(X_{0}\) and \(\#_{0}(X_{0})=1\). If the tree is modified according to point (2) of the definition, this refers to Lemma 5, where \(\#_{i+1}(X)\leq\#_{i}(Z)\) and \(\#_{i+1}(Z)\leq\#_{i}(Z)+1\) is shown when a rule \(X\to Z^{d}\) for \(d\geq 2\) is introduced. The _level_ of a node is the length of the path from the node to the root. For a unary nonterminal \(X\in N_{i}\), we denote by \(\mathsf{level}_{i}(X)\) the level of the unique leaf of \(T_{i}\) that is labeled with \((X,k)\) for some \(k\). Example 3: _Assume that the first three rules introduced by a global algorithm are \(X_{2}\to X_{0}^{d_{1}}\) in the first round, \(X_{1}\to X_{0}^{d_{2}}\) in the second round and \(X_{3}\to X_{2}^{d_{3}}\) in the third round for \(d_{1},d_{2},d_{3}\geq 2\).