# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 3 Upper Bound for Greedy  
To show our improved upper bound for the approximation ratio of Greedy on unary words, we are first going to prove that the size of the SLP produced by Greedy for the input \(a^{n}\) is upper-bounded by \(\mathcal{O}((\log n)^{9}\cdot(\log\log n)^{3}\). **Proposition 1**. : _For all \(n\), we have_  
\[|\mathsf{Greedy}(a^{n})|\in\mathcal{O}((\log n)^{9}\cdot(\log\log n)^{3}).\]  
First, we need to prove several lemmas that are fulfilled for any global algorithm. When we apply specific arguments to Greedy, we draw attention to it. For better readability, we will use \(X_{0}=a\), i.e., the input is \(X_{0}^{n}\). Furthermore, let \(\mathbb{A}_{i}=(N_{i},\{X_{0}\},P_{i},S)\) be the SLP obtained by the global algorithm on input \(X_{0}^{n}\) after \(i\) rounds. Please note that until the algorithm stops, we have \(|N_{i}\setminus\{S\}|=i\) since exactly one new nonterminal is introduced in each round. If we quantify over the rounds of the algorithm, we always implicitly mean that the statements hold until the algorithm stops. If \(i\) is mentioned without a quantification, then the statement holds for any \(\mathbb{A}_{i}\) constructed after some round \(i\) of the algorithm. **Lemma 2**. : _For every \(i\), there is a fixed order \(X_{i}>X_{i-1}>\cdots>X_{1}\) of the nonterminals in \(N_{i}\setminus\{S\}\) such that every right-hand side of a rule \((X\to v)\in P_{i}\) satisfies_  
\[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]  
Proof. : We prove this property by induction. Initially, the property holds for the SLP \(\mathbb{A}_{0}\) since \(N_{0}\setminus\{S\}=\emptyset\) and the only rule \(S\to X_{0}^{n}\) satisfies \(X_{0}^{n}\in X_{0}^{s}\). Now assume the claim is true for \(\mathbb{A}_{i}\), i.e., each right-hand side of a rule in \(P_{i}\) is a word from \(X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}\). Please note that any nonempty factor of such a right-hand side is a word from \(X_{k}^{s}\cdots X_{j+1}^{s}X_{j}^{+}\) for some \(i\geq k>j\geq 0\). Therefore, assume the global algorithm chooses a maximal string \(\gamma\in X_{k}^{s}\cdots X_{j+1}^{s}X_{j}^{+}\) in round \(i+1\) and \((X\to\gamma)\in P_{i+1}\) is the corresponding new rule. We show that \(v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{i}^{s}X_{j}^{+}\cdots X_{1}^{s}X_{0}^{s}\) for all rules \((Y\to v)\in P_{i+1}\), i.e., the order of the nonterminals after round \(i+1\) is obtained by inserting the new nonterminal \(X\) directly before \(X_{j}\) in the previous order. First, this is obviously true for the new rule \(X\to\gamma\) as well as for all rules that have not been modified during round \(i+1\). It remains to check the rules \((Y\to v)\in P_{i+1}\) that are obtained from a rule \((Y\to v^{\prime})\in P_{i}\) by replacing a largest set of pairwise nonoverlapping occurrences of \(\gamma\) in \(v^{\prime}\) by the new nonterminal \(X\). If \(\gamma=X_{j}^{d}\) (\(d\geq 2\)) is unary and \(X_{j}^{\ell}\) is the single maximal \(X_{j}\)-block that occurs in \(v^{\prime}\), then replacing occurrences of \(\gamma\) from left to right yields \(X^{\ell}\operatorname{div}^{d}X_{j}^{\ell}\)\(\operatorname{mod}^{d}\) as the new maximal blocks of \(X\) and \(X_{j}\) in \(w\). It follows that \(v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{i}^{s}\cdots X_{1}^{s}X_{0}^{s}\). If otherwise \(\gamma\) is not a unary word, i.e., \(\gamma\in X_{k}^{+}\cdots X_{j+1}^{s}X_{j}^{+}\) for \(i\geq k>j\geq 0\), then \(v^{\prime}\) has exactly one occurrence of \(\gamma\) as a factor. It follows that \(v\in X_{i}^{*}X_{i-1}^{*}\cdots X_{k}^{*}XX_{j}^{*}\cdots X_{1}^{*}X_{0}^{*}\) and thus \(v\) satisfies the claim. This finishes the induction. In other words, there is at most one maximal block for each symbol on each right-hand side and the order of these blocks is the same for all rules. Similar to the case distinction in the last steps of the proof of Lemma 2, we will distinguish two types of nonterminals. Let \(X\to\gamma\) be the introduced rule in some round of the algorithm. If \(\gamma\) is unary, then we call \(X\) a unary nonterminal.