# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 3 Upper Bound for Greedy
We first show that if \(k:=|M_{j}\cap M|\geq 2\), then \(s(j+1)\leq s(j)\). In other words, if two nonunary nonterminals occur in \(\gamma\), then \(s(j+1)\leq s(j)\). Let \(r\) be the number of rules \((Z\to v)\in P_{j}\) such that \(\gamma\) is a factor of \(v\). Recall that nonunary factors and nonterminals occur at most once on the right-hand side of a single rule (Lemma 3). We have \(s(j+1)-s(j)=k+r-k\cdot r\) because the new nonunary nonterminal \(X\) occurs now on \(r\) right-hand sides, \(\gamma\) contains \(k\) nonunary nonterminals which occur exactly once in \(\gamma\) each, and the replacement of \(\gamma\) on right-hand sides deletes these \(k\) nonterminals on \(r\) right-hand sides. We have \(r\geq 2\) (due to the properties of a maximal string) which together with \(k\geq 2\) yields \(s(j+1)-s(j)\leq 0\). Hence we can assume that \(k=|M_{j}\cap M|\leq 1\). The maximal string \(\gamma\) has length \(|\gamma|\geq 2\) and is not unary, so the first and the last symbol of \(\gamma\) are different and at least one of them is unary due to our assumption that at most one nonunary nonterminal occurs in \(\gamma\). Let \(Y\) be this unary nonterminal and assume that \(Y\) is the first symbol, i.e., the nonunary, maximal string is \(\gamma=Y\gamma\) for some (nonempty) \(v\). Afterwards we discuss the case where \(Y\) is the last symbol, i.e., \(\gamma=vY\). We bound the number of rounds where a nonunary, maximal string \(\gamma=Yv\) is selected for some \(v\). Let \(j_{0}\leq i\) be the round where the unary nonterminal \(Y\) has been introduced. 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}\]4  
due to Lemma 6 and \(\mathsf{level}_{j}(Y)\leq\mathsf{level}_{i}(Y)\) for all \(j\leq i\). We also have \(f_{j+1}(Y)\leq f_{j}(Y)\) for \(j\in[j_{0},i-1]\) by Lemma 10. In addition to that, if \(Yv\) is the selected nonunary, maximal string in round \(j+1\) for some \(v\), then we have \(f_{j+1}(Y)<f_{j}(Y)\) again by Lemma 10. It follows that after at most \(\mathsf{level}_{i}(Y)+1\) many rounds where the chosen maximal string is nonunary and has the form \(Yv\) for some (nonempty) \(v\), we have \(f_{i}(Y)=0\). In this case, all maximal \(Y\)-blocks have distinct right neighbors or occur at the end of a right-hand side. Hence there is no possibility to select a nonunary, maximal string \(Yv\) anymore. Now we similarly bound the number of rounds such that a nonunary, maximal string \(\gamma=vY\) is selected for some \(v\). However, care must be taken in this case, because it is possible that \(g_{j+1}(Y)>g_{j}(Y)\) when a rule \(X^{t}\to Y^{d}\) for \(d\geq 2\) is introduced in round \(j+1\) as explained above. Fortunately, rules of this form (the selected maximal string is from \(Y^{+}\)) are introduced at most \(\mathsf{level}_{i}(Y)\) many times up to round \(i\) by the definition of \(\mathsf{level}_{i}(Y)\). Let \(j_{0}\leq i\) be the round where the unary nonterminal \(Y\) has been introduced. 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}\]5  
for each \(j\in[j_{0},i]\) due to Lemma 6 and \(\mathsf{level}_{j}(Y)\leq\mathsf{level}_{i}(Y)\) for all \(j\leq i\). Furthermore, if the selected maximal string in round \(j+1\) (\(j\geq j_{0}\)) is not from \(Y^{+}\), we have \(g_{j+1}(Y)\leq g_{j}(Y)\) due to Lemma 11. Moreover, if the maximal string \(\gamma\) is nonunary and \(\gamma=vY\) for some (nonempty) \(v\), then \(g_{j+1}(Y)<g_{j}(Y)\). It follows that between two rounds where maximal strings from \(Y^{+}\) are selected, there are at most \(\mathsf{level}_{i}(Y)+1\) many rounds where a nonunary, maximal string of the form \(vY\) is chosen because then \(g_{j}(Y)=0\) is reached (for some \(j\)) and thus all maximal \(Y\) blocks have distinct left neighbors or occur at the beginning of a right-hand side. Hence no nonunary string of the form \(vY\) for some \(v\) occurs twice on right-hand sides.