## 7 Tree Comparison and Related Problems
### Classical Tree Edit Distance  
The classical tree edit model is, akin to tree alignment, defined more generally on forests. As before, we follow the tradition to discuss it as a problem on trees. While the tree alignment model computes an optimal common supertree for its inputs, the tree edit model computes an optimal common subtree. (In the present discussion, a subtree is a sub-set of tree nodes, preserves ancestorship and order, but need not be contiguous.) This subtree is given by an injective mapping that respects the tree structure. Essentially, the mapped nodes are the rep-nodes in a tree alignment, whereas the del or ins nodes are not represented. Each tree alignment can be converted into a tree edit mapping by deleting all insertion and deletion nodes, while the converse is not true: Certain mappings cannot be embedded in a common supertree. The example used in Figure 11 is a case in point. There, we can map all nodes carrying the same label onto each other, but we cannot embed this mapping in a tree alignment. Thus, for a given pair of trees, the tree edit model has a larger search space than the tree alignment model, and whether or not this is desirable depends on the application. Figure 11: Graphical view of tree alignment with oscillating gaps. Core operators mty and \(\sim\) are not shown. Note that after the gap opening for the deletion of \(e\), oscillation allows for a gap extension when inserting \(f\). In this core term, the top rep node and the open_del are derived from nonterminal symbol \(N\), the two ins nodes from \(S\), and the others from \(P\). Different algorithms for computing edit distance on trees have ben reported [40, 41]. They implement the same model, but use different problem decompositions. Hence, the recurrences which implement them appear quite different. Specifying the tree edit distance problem by an ICORE, we remain independent of implementation details, and this can be seen as a specification of either of these algorithms. Conversely, the known algorithms witness the implementability of this ICORE, and the implementation freedom it allows for. For the input forests, we can re-use our satellite signature _TREE_, and for mappings, the core signature _TreeAl_. While the former is obvious, the latter may come as a surprise. Though mappings cannot always be embedded in supertrees, they can be represented by _TreeAl_ terms together with a suitable set of rewrite rules. This paradox is resolved below. In ICORE TreeEdit on page 119, we re-use algebra TreeSimilarity; a common convention is \(\delta=\gamma=0\), such that only the mapped nodes contribute to the score. **Example 18**. : _Reconsider the trees \(a(e(b{\sim}c){\sim}d)\) and \(a(b{\sim}f(c{\sim}d))\) of Figure 11. Under a reasonable choice of score, the optimal tree edit maps the nodes labeled \(a\), \(b\), \(d\), and also \(c\) onto each other, with an optimal score of \(w(a,a)+w(b,b)+w(c,c)+w(d,d)\). The edit distance between \(a(e(b{\sim}c){\sim}d)\) and \(a(b{\sim}f(c{\sim}d))\) is achieved by the core term \(t=\)_  
\[ \begin{array}{c}\underline{\mbox{rep}}(a,a,\underline{\mbox{del}}(e, \underline{\mbox{rep}}(b,b,\underline{\mbox{mty}}){\sim}\underline{\mbox{ ins}}(f,\underline{\mbox{rep}}(c,c,\underline{\mbox{mty}}){\sim}\underline{\mbox{rep}}(d,d, \underline{\mbox{mty}}))))\\ \downarrow\\ a(\underline{\mbox{del}}(e,b{\sim}\underline{\mbox{ins}}(f,c{\sim}d)))\\ \swarrow\\ a(\underline{\mbox{del}}(e,b{\sim}c{\sim}d))\\ \downarrow\\ a(e(b{\sim}c){\sim}d)\\ \end{array} \]  
In our diagram, rewriting positions are underlined. The first line summarizes four applications of the replacement rule at independent subterms of \(t\). The following steps make use of _associative_ rewriting. In line 2, \(c{\sim}d\) is grouped as \((c{\sim}d){\sim}\texttt{mty}\) to match the rule for ins. In line 3, \(b{\sim}c{\sim}d\) is grouped as \((b{\sim}c){\sim}d\) to match the rule for del. The use of associative rewriting is essential to accommodate the tree edit model in the ICORE framework.