# Compressed Communication Complexity of _Hamming Distance_
## 3 Compressed Communication Complexity of _Hamming Distance_
### On the Sizes of Non-Self-Referencing LZ77 Factorization of Suffix
#### 3.1.2 Upper Bound for \(\zeta(n)\)  
Next, we consider an upper bound for \(\zeta(n)\). The tools we use here are the \(C\)-factorization [9] without self-references, and a grammar compression called _AVL-grammar_[10]. **Definition 3** (Non-self-referencing C-factorization). : _The non-self-referencing C-factorization of string \(S\), denoted \(\mathsf{CN}(S)\), is a factorization \(S=c_{1}\cdots c_{\mathsf{cn}}\) that satisfies the following: Let \(w_{i}\) denote the beginning position of each factor \(c_{i}\) in the factorization \(c_{1}\cdots c_{\mathsf{cn}}\), that is, \(w_{i}=|c_{1}\cdots c_{i-1}|+1\). (1) If \(i>1\) and \(\max_{1\leq i<w_{i}}\{\operatorname{\mathsf{lcp}}(S[w_{i}..],S[j..w_{i}-1])\}\geq 1\), then for any position \(r_{i}\in\operatorname*{arg\,max}_{1\leq j<w_{i}}\operatorname{\mathsf{lcp}} (S[w_{i}..],S[j..w_{i}-1])\) in \(S\), let \(y_{i}=\operatorname{\mathsf{lcp}}(S[w_{i}..],S[r_{i}..w_{i}-1])-1\). (2) Otherwise, let \(y_{i}=0\). Then, \(c_{i}=S[w_{i}..w_{i}+y_{i}]\) for each \(1\leq i\leq\mathsf{cn}\)._  
The _size_\(\mathsf{cn}(S)\) of \(\mathsf{CN}(S)\) is the number \(\mathsf{cn}\) of factors in \(\mathsf{CN}(S)\). **Example 3**. : For \(S=\texttt{abaababaabaabaabaabaabab}\), \(\mathsf{CN}(S)=\texttt{a}\mid\texttt{b}\mid\texttt{a}\mid\texttt{ab}\mid \texttt{abaab}\mid\texttt{a}\texttt{aba}\mid\texttt{abaaba}\mid\texttt{b}\mid\) and its size is \(8\). The difference between \(\mathsf{LZN}(S)\) and \(\mathsf{CN}(S)\) is that while each factor \(f_{i}\) in \(\mathsf{LZN}(S)\) is the shortest prefix of \(S[u_{i}..]\) that does not occur in \(S[1..u_{i}-1]\), each factor \(c_{i}\) in \(\mathsf{CN}(S)\) is the longest prefix of \(S[w_{i}..]\) that occurs in \(S[1..w_{i}-1]\). This immediately leads to the next lemma. **Lemma 3**. : _For any string \(S\), \(\mathsf{cn}(S)\geq\texttt{zn}(S)\)._  
We also use the next lemma in our upper bound analysis for \(\zeta(n)\). **Lemma 4**. : _For any string \(S\), \(\mathsf{cn}(S)\leq 2\texttt{zn}(S)\)._  
Proof. : Suppose that there are two consecutive factors \(c_{i},c_{i+1}\) of \(\mathsf{CN}(S)\) and a factor \(f_{j}\) of \(\mathsf{LZN}(S)\) such that \(c_{i},c_{i+1}\) are completely contained in \(f_{i}\) and the ending position of \(c_{i+1}\) is less than the ending position of \(f_{j}\). Since \(c_{i}c_{i+1}\) is a substring of \(f_{j}[..|f_{j}|-1]\) and \(f_{j}[..|f_{j}|-1]\) has a previous occurrence in \(f_{1}\cdots f_{j-1}\), this contradicts that \(c_{i}\) terminated inside \(f_{j}[..|f_{j}|-1]\). Thus, the only possible case is that \(c_{i}c_{i+1}\) occurs as a suffix of \(f_{j}\). Please note that in this case \(c_{i-1}\) cannot occur inside \(f_{j}\) by the same reasoning as above. Therefore, at most two consecutive factors of \(\mathsf{CN}(S)\) can occur completely inside of each factor of \(\mathsf{LZN}(S)\). This leads to \(\mathsf{cn}(S)\leq 2\texttt{zn}(S)\). An AVL-grammar of a string \(S\) is a kind of a _straight-line program_ (_SLP_), which is a context-free grammar in the Chomsky-normal form which generates only \(S\). The parse-tree of the AVL-grammar is an AVL-tree [17] and therefore, its height is \(O(\log n)\) if \(n\) is the length of \(S\). Let \(\mathsf{avl}(S)\) denote the size (i.e., the number of productions) in the AVL-grammarfor \(S\). Basically, the AVL-grammar for \(S\) is constructed from the C-factorization of \(S\), by introducing at most \(O(\log n)\) new productions for each factor in the C-factorization. Thus, the next lemma holds. **Lemma 5** ([10]). : _For any string \(S\) of length \(n\), \(\mathsf{avl}(S)=O(\mathsf{cn}(S)\log n)\)._  
Now we show our upper bound for \(\zeta(n)\). **Lemma 6**. : \(\zeta(n)=O(\log n)\)_._  
Proof. : Suppose we have two AVL-grammars for strings \(X\) and \(Y\) of respective sizes \(\mathsf{avl}(X)\) and \(\mathsf{avl}(Y)\). [PERSON] [10] showed how to build an AVL-grammar for the concatenated string \(XY\) of size \(\mathsf{avl}(X)+\mathsf{avl}(Y)+O(h)\), where \(h\) is the height of the taller parse-tree of the two AVL-grammars before the concatenation.