# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 3 Upper Bound for Greedy
If \(X\) does not occur in \(\gamma\), then it is straightforward to see that \(f_{i+1}(X)\leq f_{i}(X)\) since \(\#_{i+1}(X)=\#_{i}(X)\) and \(R_{i+1}(X)\geq R_{i}(X)\). The new nonterminal \(Y\) could be a new right neighbor for some occurrences of \(X\), but all occurrences of \(X\) which have this new right neighbor \(Y\) in \(\mathbb{A}_{i+1}\) shared the same right neighbor in \(\mathbb{A}_{i}\) (the first symbol of \(\gamma\)). If otherwise \(X\) occurs in \(\gamma\), then first assume that \(\gamma=X^{d}\) for some \(d\geq 2\). Please note that replacing an occurrence of \(\gamma\) on the right-hand side of a rule \((Z\to u)\in P_{i}\) either removes all occurrences of \(X\) on this right-hand side (in case \(u\) contains a maximal \(X\)-block of length \(k\cdot d\) for some integer \(k\geq 1\)) or the right neighbor of the maximal \(X\)-block in \(u\) does not change in the modified rule \((Z\to u^{\prime})\in P_{i+1}\) since occurrences of \(\gamma\) are replaced from left to right. It follows that the only way to obtain \(R_{i+1}(X)<R_{i}(X)\) is to remove all occurrences of \(X\) on a right-hand side, but then \(\#_{i}(X)\) decreases by the same value. Additionally, the new rule \(Y\to X^{d}\) adds a new right-hand side to \(\#_{i+1}(X)\), but since \(X\) is the last symbol on this right-hand side it follows that \(R_{i+1}(X)\) is incremented as well. Together this yields \(f_{i+1}(X)\leq f_{i}(X)\) in this case. The case remains where \(\gamma\) is nonunary and \(X\) occurs in \(\gamma\). Here, 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. However, again, the only way to reduce \(R_{i+1}(X)\) compared to \(R_{i}(X)\) is to remove all occurrences of \(X\) on a right-hand side, but then again \(\#_{i+1}(X)\) decreases by the same value. This yields \(f_{i+1}(X)\leq f_{i}(X)\). Assume now that a nonunary, maximal string \(\gamma=Xv\) for some \(v\in(N_{i}\cup\{X_{0}\})^{+}\) is selected in round \(i+1\). We show that \(f_{i+1}(X)<f_{i}(X)\). If \(X\) only occurs in the new rule in \(\mathbb{A}_{i+1}\) after occurrences of \(\gamma\) are replaced on all right-hand sides in \(\mathbb{A}_{i}\), i.e., all modified rules do not contain \(X\) anymore, then \(\#_{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-handside which contains \(X\) to \(\#_{i+1}(X)\). Also, we have \(R_{i+1}(X)=R_{i}(X)\) in this case and thus \(f_{i+1}(X)<f_{i}(X)\) because all rules where the maximal \(X\)-block is removed shared the same right neighbor due to the fact that \(\gamma=Xv\) is the chosen maximal string. However, \(Xv\) still occurs in the new rule of \(\mathbb{A}_{i+1}\) and thus \(R_{i+1}(X)=R_{i}(X)\). If otherwise at least one of the modified rules still contains \(X\) on the right-hand side, then \(XY\) is a factor of this right-hand side in \(\mathbb{A}_{i+1}\) after the replacement of \(\gamma\). It follows that \(R_{i+1}(X)>R_{i}(X)\) in this case and thus \(f_{i+1}(X)<f_{i}(X)\) because each distinct right neighbor of \(X\) in \(\mathbb{A}_{i}\) is still a right neighbor of \(X\) in \(\mathbb{A}_{i+1}\) as argued above, but additionally \(XY\) is new since \(Y\) is a new nonterminal. The same result does not hold for \(g_{i}(X)\). In particular, \(g_{i+1}(X)>g_{i}(X)\) is possible when a rule \(Y\to X^{d}\) is introduced in round \(i+1\) for some \(d\geq 2\) due to the assumption that global algorithms replace occurrences of the maximal string from left to right. For example, assume that \(AX^{d}\), \(BX^{\gamma}\) and \(CX^{10}\) are the maximal \(X\)-blocks on right-hand sides of \(\mathbb{A}_{i}\) including distinct left neighbors for each \(X\)-block (\(A\), \(B\) and \(C\)). Therefore, we have \(\#_{i}(X)=3\), \(L_{i}(X)=3\) and thus \(g_{i}(X)=0\) in this example. If now a rule \(Y\to X^{3}\) is introduced, then this yields \(AYX\), \(BY^{2}X\) and \(CY^{3}X\) after replacing \(X^{3}\).