# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 3 Upper Bound for Greedy
Hence we have \(\#_{i+1}(X)=4\), \(L_{i+1}(X)=2\) and thus \(g_{i+1}(X)=2\). We show in the following lemma that this is the only case where \(g_{i+1}(X)>g_{i}(X)\) occurs. Lemma 11: _Let \(X\in N_{i}\cup\{X_{0}\}\). If a rule \(Y\to\gamma\) is introduced in round \(i+1\) such that \(\gamma\
otin X^{+}\), then \(g_{i+1}(X)\leq g_{i}(X)\). If a nonunary, maximal string \(\gamma=Xv\) is selected in round \(i+1\) for some \(v\in(N_{i}\cup\{X_{0}\})^{+}\), then \(g_{i+1}(X)<g_{i}(X)\)_  
Proof. : The arguments are similar to the corresponding cases in Lemma 10. Let \(Y\to\gamma\) be the introduced rule in round \(i+1\). If \(X\) does not occur in \(\gamma\), then \(g_{i+1}(X)\leq g_{i}(X)\) since \(\#_{i+1}(X)=\#_{i}(X)\) and \(L_{i+1}(X)\geq L_{i}(X)\). The new nonterminal \(Y\) could be a new left neighbor for some occurrences of \(X\) in \(\mathbb{A}_{i+1}\), but all these occurrences of \(X\) shared the same left neighbor in \(\mathbb{A}_{i}\) (the last symbol of \(\gamma\)). If otherwise \(\gamma\) is nonunary and contains \(X\), then we have \(\#_{i+1}(X)\leq\#_{i}(X)\) due to Lemma 4 and \(\gamma\) occurs at most once on each right-hand side due to Lemma 2. The only way to obtain \(L_{i+1}(X)<L_{i}(X)\) is again to remove all occurrences of \(X\) on a right-hand side, but then \(\#_{i+1}(X)\) decreases by the same value. Please note that due to the assumption that \(\gamma\) is nonunary, it is not possible to modify two (or more) rules such that the maximal \(X\)-blocks have different left neighbors in \(\mathbb{A}_{i}\) and after the replacement these \(X\)-blocks share the same left neighbor in \(\mathbb{A}_{i+1}\). This yields \(g_{i+1}(X)\leq g_{i}(X)\). Assume now that a nonunary, maximal string \(\gamma=vX\) is selected in round \(i+1\) for some word \(v\in(N_{i}\cup\{X_{0}\})^{+}\). We show that \(g_{i+1}(X)<g_{i}(X)\). If \(X\) only occurs in the new rule in \(\mathbb{A}_{i+1}\), i.e., \(X\) does not occur in the modified rules, then we have \(\#_{i+1}(X)<\#_{i}(X)\) because at least two right-hand sides do not contain \(X\) as a factor anymore while only the new rule \(Y\to\gamma\) adds a new right-hand side which contains \(X\) to \(\#_{i+1}(X)\). Moreover, we have \(L_{i+1}(X)=L_{i}(X)\) in this case because all rules where the maximal \(X\)-block is removed shared the same left neighbor since \(\gamma=vX\) is the selected nonunary, maximal string. However, \(vX\) still occurs on the right-hand side of the new rule of \(\mathbb{A}_{i+1}\). It follows that \(g_{i+1}(X)<g_{i}(X)\). If otherwise at least one of the modified rules still contains \(X\) on the right-hand side, then \(YX\) is a factor of this right-hand side in \(\mathbb{A}_{i+1}\) after the replacement of \(\gamma\). It follows that \(L_{i+1}(X)>L_{i}(X)\) and thus \(g_{i+1}(X)<g_{i}(X)\) because each distinct left neighbor of \(X\) in \(\mathbb{A}_{i}\) is still a left neighbor of \(X\) in \(\mathbb{A}_{i+1}\) for some occurrence of \(X\). Additionally, \(Y\) is a new left neighbor. In the following proof, we use the notation  
\[M=\{Y\in N_{i}\mid(Y\to v)\in P_{i}\text{ and }\gamma\text{ is a factor of }v\}\subseteq N_{i}\]2  
for all unary nonterminals that appear in \(\mathbb{A}_{i}\) and \(M_{i}=N_{i}\setminus U_{i}\) for all nonunary nonterminals that appear in \(\mathbb{A}_{i}\). **Lemma 12**. : _We have_  
\[M=\{Y\in N_{i}\mid(Y\to v)\in P_{i}\text{ and }\gamma\text{ is a factor of }v\}\subseteq N_{i}\]3  
Proof. : Let \(s(i)=\sum_{X\in M_{i}}t_{i}(X)\) be the total size that all nonunary nonterminals contribute to the size of \(\mathbb{A}_{i}\). We first bound the number of rounds where the function \(s\) increases, i.e., we bound \(|\{j\in[0,i-1]\mid s(j+1)>s(j)\}|\). If a unary nonterminal is introduced in some round \(j+1\), then \(s(j+1)=s(j)\), i.e., we can ignore these rules. So, consider some round \(j+1\) where a nonunary nonterminal \(X\) is introduced and let \(X\to\gamma\) be the introduced rule. Let \(M=\{Z\in N_{j}\mid Z\text{ occurs in }\gamma\}\) be the set of nonterminals that occur at least once in \(\gamma\).