## 7 Tree Comparison and Related Problems
### Tree Alignment under a Generalized Edit Model
Before we embark on the construction of ICOREs from generalized edit operations, a word must be said on the difference between edit operations \(\ell\leftrightarrow r\) and rewrite rules \(\ell\to r\). Rewrite rules carry the restriction \(var(r)\subset var(\ell)\). This is because term rewriting is functional model. Rewriting a term \(s\) at a given position by \(\ell\to r\), the result is uniquely determined. Edit operations, in contrast, are a relational model. Two terms \(s\) and \(t\) may be related by an edit operation \(\ell\leftrightarrow r\), but given only \(s\) and \(\ell\leftrightarrow r\), we cannot construct \(t\). Insertions and deletions are only symmetrical operations when we know both sides, the \"source\"and the \"target\"; without a known target, we would not know what to insert with insertions. In the generalized edit model as defined above, both \(s\) and \(t\) are given, and hence, no condition is imposed on the variables in \(\ell\leftrightarrow r\). We now show how an ICORE is constructed for a generalized tree alignment problem. **Definition 6**. : _ICORE construction for a generalized tree edit problem Let \(F\) be a signature, and let \(\{(\ell_{i}\leftrightarrow r_{i},w_{i});1\leq i\leq n\}\) be a set of generalized edit operations. We define an ICORE as follows._  
* _Both satellite signatures are_ \(F\)_._
* _The core signature contains a single sort, the constant operator symbol_ \(\mathtt{mty}\)_, the alphabet of the satellite signatures (if any) as nullary operators, and_ \(2n\) _operators:_ \(\mathtt{op}^{1}_{1},\mathtt{op}^{2}_{1},\ldots,\mathtt{op}^{1}_{n},\mathtt{ op}^{2}_{n}\)_. The arity of_ \(\mathtt{op}^{1}_{i}\) _and of_ \(\mathtt{op}^{2}_{i}\) _is the cardinality s of_ \(var(\ell_{i})\cup var(r_{i})\)_._
* _For each edit operation_ \(\ell_{i}\leftrightarrow r_{i}\)_, we have two rewrite rules_ \[\ell_{i} \leftarrow \mathtt{op}^{1}_{i}(\bar{X}) \rightarrow r_{i}\] \[r_{i} \leftarrow \mathtt{op}^{2}_{i}(\bar{X}) \rightarrow \ell_{i}\] _where_ \(\bar{X}=var(\ell_{i})\cup var(r_{i})\)_._
* _The scoring algebra is_ \[\mathtt{op}^{1}_{i}(\bar{X}) = w_{i}+\bar{X}\] \[\mathtt{op}^{2}_{i}(\bar{X}) = w_{i}+\bar{X}\] \[\mathtt{mty} = 0\] \[\phi = \max\]* _The grammar accepts all core terms._  
Note that by construction, the rewrite rules are well-defined, since \(\bar{X}\) contains both \(var(\ell_{i})\) and \(var(r_{i})\). Also note that in the core signature, no associative operator is assumed, since we are heading for a generalization of the tree alignment rather the tree edit model. **Fact**: **3**. : _The above ICORE solves the tree alignment problem defined by \(\{\ell_{i}\leftrightarrow r_{i}\}\)._  
Proof. : By construction, two trees \(s\) and \(t\) are related by the edit operation \(\ell_{i}\leftrightarrow r_{i}\) applied at their root position, if and only if there is a core \(c\) term rooted by \(\mathsf{op}_{i}^{1}\) or \(\mathsf{op}_{i}^{2}\) such that \(c\) can be rewritten under the rule \(\ell_{i}\leftarrow\mathsf{op}_{i}^{1}(\bar{X})\to r_{i}\) or \(r_{i}\leftarrow\mathsf{op}_{i}^{2}(\bar{X})\rightarrow\ell_{i}\). This argument applies recursively to the other positions in the subtrees of \(s\) and \(t\). The simplest case of a generalized tree alignment problem is the classical one, using the atomic edit model. So our first example is an old friend:  
**Example 19**. : The ICORE TreeAlign for the alignment of trees is generated according to Definition 6 from the edit operations  
\[a(X) \leftrightarrow b(X)\] \[a(X) \leftrightarrow X\] \[f(X){\sim}f(Y)\leftrightarrow f(X{\sim}Y)\]0  
where \(\mathsf{op}_{1}^{1}=\mathsf{op}_{1}^{2}=\mathsf{rep}\) (the \(\mathsf{op}_{1}^{2}\) case is redundant because it produces the same rule as \(\mathsf{op}_{1}^{1}\) under exchanging \(a\) and \(b\)), \(\mathsf{op}_{2}^{1}=\mathsf{del}\), \(\mathsf{op}_{2}^{2}=\mathsf{ins}\), and \(\mathsf{op}_{3}^{1}=\mathsf{op}_{3}^{2}=\sim\) (the second case is redundant because of rule symmetry). Now let us move towards a non-trivial application the generalized tree alignment model.