## 7 Tree Comparison and Related Problems
### Tree Alignment under a Generalized Edit Model  
In our last contribution, we generalize the tree edit model to arbitrary tree edit operations, which may arise from domain-specific knowledge about what the trees represent, and properties that must be respected in an alignment. Tree alignment, as formulated above, operates on rooted, ordered, node-labeled trees. Any node label can reside anywhere in the tree, independent of context, and can have any number of subtrees. It can be aligned to any other label. Edit operations are atomic-parent nodes and their siblings are considered independently. Written as bidirectional editing rules, the classical model appears simple:  
\[ \begin{array}{ccc}a(X)&\leftrightarrow&b(X)&\mbox{-- node (label) replacement}\\ a(X)&\leftrightarrow&X&\mbox{-- node ind}\\ X{\sim}Y&\leftrightarrow&X{\sim}Y&\mbox{-- no change}\end{array} \]  
The last rule, \"no change\", was added for formal completeness, such that when editing \(s\) into \(t\), all positions can actually be edited by some rule. We are now setting out to refine this model into a _generalized tree alignment model_. Concrete applications are often richer in meaning: Some node labels imply specific others at their sibling nodes. More general edit rules are desirable, to express that some larger tree patterns should be edited as a whole into specific target patterns. An example are distributivity laws, such as  
\[f(a{\sim}g(X{\sim}Y))\leftrightarrow g(f(a{\sim}X){\sim}f(a{\sim}Y))\]  
or  
\[f(X){\sim}f(Y)\leftrightarrow f(X{\sim}Y)\]  
We want to assign a special (favourable) score to this edit operation, and to this end, it does not help that the classical model can mimic this transformation by a combination of atomic edits. A second motivation for generalization is the case where certain node labels should never be matched, because this is meaningless in our interpretation and there is no justified scoring of the result. Think of trees carrying numbers and characters at their leaves, where it makes sense to match up numbers with numbers, characters with characters, but not characters with numbers- as would be allowed in the atomic model. A penalty of \(-\infty\) for such an unwanted replacement comes to mind, but this does not remove such illegal tree alignments from the search space, it only makes them non-optimal. We want to be able to specify _generalized edit operations_, that declare explicitly what operations are allowed in place of the standard, atomic tree edit model. This is the goal of the following definitions. **Definition 5**. : _Generalized tree alignment_  
_(1) Let_ \(F\) _be a signature, and let_ \(V\) _be a set of variables. A_ generalized edit operation _is a pair of terms of_ \(T(F,V)\)_, denoted_ \(\ell\leftrightarrow r\)_, provided with a real value_ \(w\)_, called the_ weight _of the edit operation._  
_(2) The_ generalized tree alignment problem _for trees_ \(s\) _and_ \(t\) _is to find the edit script of maximal accumulated weight that transforms \(s\) to \(t\) using a given, finite set of generalized edit operations \(\{\ell_{i}\leftrightarrow r_{i}\}\)._  
Alternatively to maximizing weight, we could ask for minimizing a distance score associated with the edit operations. In the above definition, the notion of an \"edit script\" has been carried over from Section 2. This notion is yet informal and can be concretized in different ways; from here, one might strive for a generalization of the tree edit model as well as for generalized tree alignment. In either case, each position in a tree is to be involved in an edit operation exactly once; this is why we explicitly include \"no change\" rules with our edit operations. Here, our goal is a generalization of tree alignment. Hence, in the construction to follow, the core terms we will produce can be seen as data structures representing edit scripts. We will not make use of associative rewriting (cf. the discussion in Section 7.3) and we make sure by construction of our rewrite rules that the atomic tree alignment model is obtained as a special case.