## 7 Tree Comparison and Related Problems
### Classical Tree Edit Distance
This solves the paradox how we can represent a larger search space with the same core signature. A single core term can have different rewritings, depending on the use of associativity. A core term that does not rewrite to the inputs by the rules of ICORE TreeAlign may still do so by the rules of TreeEdit. Or said the other way round: In the search space for a tree edit problem, certain core terms have rewrite sequences that do not make use of associativity. They correspond to mappings that can be embedded in a common supertree of the inputs, and also represent tree alignments. However, there are additional core terms, which rewrite to the inputs modulo associativity, and they correspond to mappings that cannot be embedded. The core term in the above example, using rules from TreeAlign, rewrites to \(a(e(b){\sim}c{\sim}d)\), but not to \(a(e(b{\sim}c){\sim}d)\). Things being more sophisticated than with previous ICORES, let us supply a proof that TreeEdit actually serves its purpose. **Fact 2**. : _ICORE_TreeEdit _solves the tree edit distance problem._  
Proof. : Let \(A\) and \(B\) be two trees. We consider that a tree edit mapping between \(A\) and \(B\) is given by a common subtree, or more formally by a pairs of two isomorphic trees \(A^{\prime}\) and \(B^{\prime}\) such that \(A^{\prime}\) is embedded in \(A\) (denoted \(A^{\prime}\subseteq A\)), \(B^{\prime}\) is embedded in \(B\) (\(B^{\prime}\subseteq B\)) and \(A^{\prime}\) and \(B^{\prime}\) are identical up to the renaming of the node labels. (1) _Every rewriting of a core term indicates a mapping: Let \(t\) be a core term such that \(A\leftarrow^{+}t\rightarrow^{+}B\). Then we can deduce from \(t\) a common subtree for \(A\) and \(B\) whose cost is the same as the evaluation under the ICORE algebra for \(A\leftarrow^{+}t\rightarrow^{+}B\)._  
We define the functions \(\phi_{1}:T(TreeAl)\to T(TreeAl)\) and \(\phi_{2}:T(TreeAl)\to T(TreeAl)\) recursively as follows. \[\phi_{1}(X{\sim}Y) = \phi_{1}(X){\sim}\phi_{1}(Y)\qquad\qquad\phi_{2}(X{\sim}Y) = \phi_{2}(X){\sim}\phi_{2}(Y)\] \[\phi_{1}(a(X)) = a(\phi_{1}(X))\qquad\qquad\qquad\phi_{2}(a(X)) = a(\phi_{2}(X))\] \[\phi_{1}(\texttt{del}(a,X)) = \phi_{1}(X)\qquad\qquad\qquad\phi_{2}(\texttt{del}(a,X)) = \phi_{2}(X)\] \[\phi_{1}(\texttt{ins}(a,X)) = \phi_{1}(X)\qquad\qquad\qquad\phi_{2}(\texttt{ins}(a,X)) = \phi_{2}(X)\] \[\phi_{1}(\texttt{rep}(a,b,X)) = a(\phi_{1}(X))\qquad\qquad\qquad\phi_{2}(\texttt{rep}(a,b,X)) = b(\phi_{2}(X))\] \[\phi_{1}(\texttt{mty}) = \varepsilon\qquad\qquad\qquad\qquad\phi_{2}(\texttt{mty}) = \varepsilon\]  
First note that the only difference between \(\phi_{1}\) and \(\phi_{2}\) lies in \(\phi_{1}(\texttt{rep}\dots)\) and \(\phi_{2}(\texttt{rep}\dots)\). It follows that \(\phi_{1}(t)\) and \(\phi_{2}(t)\) are isomorphic trees. Secondly, it is straightforward to verify that for any two terms \(u\) and \(v\) such that \(u\rightarrow_{1}v\) (resp. \(u\rightarrow_{2}v\)), then \(\phi_{1}(u)\subseteq\phi_{1}(v)\) (resp. \(\phi_{2}(u)\subseteq\phi_{2}(v)\)). It follows that \(\phi_{1}(t)\subseteq\phi_{1}(A)\) and \(\phi_{2}(t)\subseteq\phi_{2}(B)\). By construction, \(\phi_{1}(A)=A\) and \(\phi_{2}(B)=B\). So the pair \((\phi_{1}(t),\phi_{2}(t))\) is a common subtree of \(A\) and \(B\). (2) _Every mapping has a core term that describes it: If there is a common subtree \((T_{1},T_{2})\) for \(A\) and \(B\), then one can construct from \((T_{1},T_{2})\) a core term \(t\) such that \(A\leftarrow^{+}t\rightarrow^{+}B\) and the rewrite derivation has the same cost as the tree mapping._We define a function \(\psi\) that takes as input two trees \(A\) and \(B\) and returns a core term \(t\), such that \(\phi_{1}(t)=T_{1}\) and \(\phi_{2}(t)=T_{2}\). Assume \(A=a(U){\sim}V\) and \(B=b(U^{\prime}){\sim}V^{\prime}\). There are three cases.