# Approximation Ratios of RePair, LongestMatch and Greedy on Unary Strings +
## 3 Upper Bound for Greedy
All other cases even satisfy \(|\mathbb{A}_{i+1}|<|\mathbb{A}_{i}|\). Point (2) directly follows. Our next goal is to bound \(t_{i}(X)\) depending on \(\mathsf{level}_{i}(X)\) for a unary nonterminal \(X\). To do so, we now apply arguments specific to \(\mathsf{Greedy}\). Recall that \(\mathsf{Greedy}\) selects a maximal string that minimizes the size of the obtained SLP in each round. **Lemma 8**. : _Let \(Z\in N_{i}\cup\{X_{0}\}\) be a unary nonterminal and assume a rule \(X\to Z^{d}\) for some \(d\geq 2\) is introduced by \(\mathsf{Greedy}\) in round \(i+1\). We have_  
\[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]1  
Proof. : If a unary nonterminal \(X\) and a rule \(X\to Z^{d}\) with \(d\geq 2\) are introduced in round \(i+1\), then the choice of \(d\) only depends on the maximal \(Z\)-blocks occurring on all right-hand sides of rules in \(\mathbb{A}_{i}\) since the remaining part of \(\mathbb{A}_{i}\) does not change. Assume that \(\#_{i}(Z)=k\) and let \(\ell_{1},\ldots,\ell_{k}\) be the lengths of the maximal \(Z\)-blocks occurring on right-hand sides of \(\mathbb{A}_{i}\), i.e., \(\sum_{j=1}^{k}\ell_{j}=t_{i}(Z)\). Then \(\mathsf{Greedy}\) minimizes \(t_{i+1}(X)+t_{i+1}(Z)=d+\sum_{j=1}^{k}(\ell_{j}\text{ div }d)+(\ell_{j}\text{ mod }d)\), where \(d\) is the size of the new rule \(X\to Z^{d}\) and for each \(j\in[1,k]\) a maximal block \(Z^{\ell_{j}}\) on the right-hand side of a rule in \(\mathbb{A}_{i}\) is transformed into \(X^{\ell_{j}\text{ div }d}Z^{\ell_{j}\text{ mod }d}\). Due to the greedy nature of the algorithm, the following equation holds for all \(d\geq 1\):  
\[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]2 \[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]3 \[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]4  
Please note that the chosen maximal string has length at least 2, but the upper bound also holds for \(d=1\) since in this case we have \(t_{i+1}(X)+t_{i+1}(Z)\leq t_{i}(Z)\) due to Lemma 7 (point (2)). If we apply \(d=\left\lceil\sqrt{t_{i}(Z)}/\sqrt{k+1}\right\rceil\), we get  
\[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]5 \[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]6 \[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]7 \[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]8  
Together with \(k=\#_{i}(Z)\) this proves the lemma. The following lemma is essential for the proof of Theorem 1 since we bound the total number of occurrences of a unary nonterminal depending on its level. **Lemma 9**. : _Let \(X\in N_{i}\cup\{X_{0}\}\) be a unary nonterminal with \(\mathsf{level}_{i}(X)=m\). We have_  
\[v\in X_{i}^{s}X_{i-1}^{s}\cdots X_{1}^{s}X_{0}^{s}.\]9Proof. : We prove the lemma by induction on \(m=\mathsf{level}_{i}(X)\) and we start with \(m=0\). The only \(\mathrm{SLP}\,\mathbb{A}_{i}\) that contains a unary nonterminal \(X\) such that \(\mathsf{level}_{i}(X)=0\) is the initial \(\mathbb{A}_{0}\) and the unary nonterminal is \(X=X_{0}\). Please note that the maximal string \(\gamma\) chosen by any global algorithm in the first round on input \(X_{0}^{n}\) trivially satisfies \(\gamma\in X_{0}^{n}\) and thus the two unary nonterminals of \(\mathbb{A}_{1}\) have level one. We have \(t_{0}(X_{0})=n\) and this is exactly what we obtain when \(m=0\) is used on the right side of Equation (1) (the empty product is considered to be 1). Now assume any unary nonterminal that has level \(m\) satisfies the claimed bound and we consider a unary nonterminal \(X\) such that \(\mathsf{level}_{i}(X)=m+1>0\) for some \(i\). It follows from the definition that there is a leaf node at level \(m+1\) in \(T_{i}\) that is labeled with \((X,k)\) for some \(k\). There are two cases that need to be distinguished. Either this leaf is a left child or a right child of its parent node. Assume that \((X,k)\) is the label of a right child and let \((Z,k+1)\) be the label of the left sibling of that node. To prove both cases simultaneously, we prove the upper bound for \(X\) and for \(Z\), i.e., we use \(Z\) to cover the second case where the node is a left child.