## 7 Tree Comparison and Related Problems
### Classical Tree Edit Distance
- If \(a\) occurs in \(T_{1}\) and \(b\) in \(T_{2}\): \(\psi(a(U){\sim}V,b(U^{\prime}){\sim}V^{\prime})\ =\ \texttt{rep}(a,b,\psi(U,U^{\prime})){ \sim}\psi(V,V^{\prime})\)  
- if \(a\) is not in \(T_{1}\): \(\psi(a(U){\sim}V,b(U^{\prime}){\sim}V^{\prime})\ =\ \texttt{del}(a,\psi(U{\sim}V,b(U^{\prime}){ \sim}V^{\prime}))\)  
- if \(b\) is not in \(T_{2}\): \(\psi(a(U){\sim}V,b(U^{\prime}){\sim}V^{\prime})\ =\ \texttt{ins}(b,\psi(a(U){\sim}V,U^{\prime}{ \sim}V^{\prime}))\)  
Note that the two last cases overlap, when neither \(a\) nor \(b\) are in the mapping. In this case, the construction is ambigous, and it is possible to apply the insertion rule before the deletion rule, or vice-versa. The fact that \(A\ {\leftarrow}^{+}\ \psi(A,B)\ {\rightarrow}^{+}\ B\) is proven by induction on the size of \(A\) and \(B\). For example, if \(\psi(A,B)\) is of the form \(\texttt{del}(a,w)\) with \(w=\psi(U{\sim}V,b(U^{\prime}){\sim}V^{\prime})\), we have by induction hypothesis \(U{\sim}V\ {\leftarrow}^{+}\ w\ {\rightarrow}^{+}\ b(U^{\prime}){ \sim}V^{\prime}\), hence  
\[a(U){\sim}V\ {\leftarrow}\ \texttt{del}(a,U{\sim}V)\ {\leftarrow}^{+}\ \texttt{del}(a,w)\ { \rightarrow}^{+}\ \texttt{del}(a,b(U^{\prime}){\sim}V^{\prime})\ {\rightarrow}\ b(U^{\prime}){ \sim}V^{\prime}\]  
Other cases are similar. It is worth noticing that the rewrite steps in this inductive proof are bottom-up: the rewriting first eliminates operator symbols at the leaves of the term, and so on. Rewritings that proceed top-down may take \"wrong\" turns and not arrive at the input trees. The bottom-up strategy may be useful to keep in mind for implementing ICOREs. Relation to sequence comparison.As tree edits determine an optimal common subtree, their counterpart on sequences is the optimal common subsequence. This is also known as a sequence \"trace\", and is different from sequence alignment, as the order of adjacent indels between matched residues remains unspecified-see also grammar AffiTrace for ICORE Affine. When specializing trees to sequences, we can again apply the non-branching-tree or the forest-of-leaves view. In the first view, the variable \(Y\) always matches to \(\texttt{mty}\), which is rewritten to \(\varepsilon\). In the forest-of-leaves view, this holds for the variable \(X\). Deleting either \(X\) or \(Y\) from all rules except Equation (16) gives rules that resemble those of sequence alignment (ICORE EditDistance, cf. Section 5) in either the linear tree or the forest-of-leaves representation. In either case, all core terms sharing the same set of replacements represent the same common subsequence, while they represent different sequence alignments. Affine gap weights.Once we consider an edit distance model where indels contribute to the score, we might as well consider the generalized gap models of the previous section. Since the core signature for TreeEdit is the same as for TreeAliGeneric, we can extend it to TreeAliAffine and use the same grammars for the same gap modes: CompleteSubtree, CompleteSubforest, Subtree, Subforest. Note that the rewrite rules for open_del and open_ins resemble those of del and ins, as they indicate the same situation, only with a different score. Convex gap weights?Can we design ICOREs for tree edit distance with arbitrary convex gap weights (of which the affine weights are a special case)? In [35], [PERSON] showed that this problem is NP-hard. This means that either we cannot express arbitrary convex gap weights in our framework, or else, not all ICOREs have a polynomial time implementation (unless P = NP). This would shatter our hope for a general, polynomial-time implementation technique for ICOREs. However, note how gaps are modeled in ICOREs! They correspond to rewrite rules which, by rewriting a core term, produce a piece of input tree in one dimension, but not in the other. A single rewrite rule can only produce a gap of constant size. Successive rewrites by such rules constitute larger (composite) gaps of any size.