# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 3 Upper Bound for Greedy
Otherwise, we call \(X\)_nonunary_. We categorize \(X_{0}\) as a unary nonterminal, although formally \(X_{0}\) is not a nonterminal. Please note that the type of a nonterminal is decided when it is introduced and does not change later, i.e., even if the right-hand side of a unary nonterminal becomes nonunary during the execution of the algorithm, the type of the nonterminal stays the same. Our strategy to prove Theorem 1 is to bound the total number of occurrences of unary nonterminals and nonunary nonterminals on right-hand sides independently. It follows from Lemma 2 that every factor that occurs more than once on the right-hand side of a single rule is unary. The following lemma is a direct consequence of that fact. Lemma 3: _Every nonunary nonterminal occurs at most once on the right-hand side of each rule at any time of the algorithm._  
Corollary 1: _If a unary nonterminal \(X\) is introduced and \(X\to Z^{d}\) with \(d\geq 2\) is the corresponding rule for \(X\), then \(Z\) is a unary nonterminal._  
Next, we bound the number of rules that contain a unary nonterminal \(X\) on the right-hand side. For a nonterminal \(X\), including \(X_{0}\), let \(\#_{i}(X)\) be the number of rules of \(\mathbb{A}_{i}\) where \(X\) occurs on the right-hand side, or more formally  
\[\#_{i}(X)=|\{(Y\to v)\in P_{i}\mid X\text{ occurs in }v\}|.\]  
The next two lemmas describe how \(\#_{i}\) evolves depending on the type of the introduced nonterminal. Lemma 4: _If a nonunary nonterminal \(X\) is introduced in some round \(i+1\), then for every \(X^{\prime}\
eq X\) (including \(X_{0}\)), we have \(\#_{i+1}(X^{\prime})\leq\#_{i}(X^{\prime})\)._  
Proof: To prove this point, we use that all rules \((Y\to v)\in P_{i}\) satisfy \(v\in X_{i}^{*}X_{i-1}^{*}\cdots X_{1}^{*}X_{0}^{*}\) (Lemma 2). Since \(X\) is nonunary, the chosen maximal string \(\gamma\) satisfies \(\gamma\in X_{k}^{*}\cdots X_{j+1}^{*}X_{j}^{*}\) for \(i\geq k>j\geq 0\). If a nonterminal \(X^{\prime}\) does not occur in \(\gamma\), then \(\#_{i+1}(X^{\prime})=\#_{i}(X^{\prime})\). So, assume the nonterminal \(X^{\prime}\) occurs in \(\gamma\), i.e., \(X^{\prime}=X_{t}\) for \(t\in[j,k]\). Note first that \(X_{t}\) occurs on the right-hand side of the new rule \((X\to\gamma)\in P_{i+1}\). It follows that to prove the claimed result, we must show that for at least one rule \((Y\to v)\in P_{i}\) such that \(X_{t}\) occurs in \(v\), all occurrences of \(X_{t}\) must disappear, i.e., \(X_{t}\) does not occur in \(v^{\prime}\) for \((Y\to v^{\prime})\in P_{i+1}\). Let  
\[M=\{Y\in N_{i}\mid(Y\to v)\in P_{i}\text{ and }\gamma\text{ is a factor of }v\}\subseteq N_{i}\]  
be the set of nonterminals of \(\mathbb{A}_{i}\) where the corresponding rule is modified in round \(i+1\). Please note that \(|M|\geq 2\) since a maximal string occurs at least twice on all right-hand sides and \(\gamma\) occurs at most once as factor of each rule since \(X\) is nonunary (Lemma 3). If \(k<t<j\) then for all \(Y\in M\) and \((Y\to v^{\prime})\in P_{i+1}\), the nonterminal \(X_{t}\) does not occur in \(v^{\prime}\) anymore since the complete \(X_{t}\)-block (among other symbols) has been replaced. This means that \(\#_{i+1}(X_{t})<\#_{i}(X_{t})\) since one new rule contains \(X_{t}\) on the right-hand side, while for at least two rules the occurrences of \(X_{t}\) have been removed in round \(i+1\). If otherwise \(t=k\) or \(t=j\), then the same argument fails since for \(Y\in M\) and \((Y\to v^{\prime})\in P_{i+1}\), the right-hand side \(v^{\prime}\) could still contain \(X_{t}\) since it is not necessarily true that the complete \(X_{t}\)-block has been replaced. However, due to the properties of a maximal string, we show that \(X_{t}\) does not occur in \(v^{\prime}\) for at least one \(Y\in M\) and \((Y\to v^{\prime})\in P_{i+1}\). Towards a contradiction, assume \(X_{t}\) occurs in \(v^{\prime}\) for all \(Y\in M\) and \((Y\to v^{\prime})\in P_{i+1}\).