# Algebraic Dynamic Programming on Trees
## 6 Tree Alignment  
Our grammar for the case of tree alignment is based on the grammars formulated in [42; 43]. We expand those grammars with explicit tree concatenation operators as shown in the previous section. This allows our algorithms to parse both trees and forests as input structures. Furthermore, we extend the grammars with the automatic derivation of an outside algorithm [24], described in Section 8. The combination of the inside and outside grammar allows for easy calculation of match probabilities. Since this is automatic, any user-defined grammar can be extended in this way as well. Though we point out that this still requires careful design of the inside grammar [7]. Representations of alignments (cf. Figure 3) are typically in the form of a tree that includes nodes from both trees, where matching nodes are given as a pair and deleted nodes from both trees are inserted in a partial-order preserving fashion. **Definition 9** (Tree alignment). : _Consider a forest \(G\) with vertex labels taken from \((\mathcal{A}\cup\{-\})\times(\mathcal{A}\cup\{-\})\) with \(\mathcal{A}\) as alphabet. Then we obtain mappings \(\pi_{1}(G)\) and \(\pi_{2}(G)\) by considering only the first or the second coordinate of the labels, respectively, and by then deleting all nodes that are labeled with the gap character '\(-\)', see Figure 3. \(G\) is an alignment of the two forests \(F_{1}\) and \(F_{2}\) if \(F_{1}=\pi_{1}(G)\) and \(F_{2}=\pi_{2}(G)\)._  
The cost of the alignment \(G\) based on the original forests \(F_{1}\) and \(F_{2}\) is the sum of the costs based on the labels in \(G\) as formulated in Equation (5). Each label consists of a pair of labels \((v_{1},v_{2})\), whereas \(v_{1}\) corresponds to a label in the vertex set of \(F_{1}\) or a gap symbol '\(-\)' and analogously for \(v_{2}\). \[\gamma(G)=\sum_{(v_{1},v_{2})\in G}\gamma_{v_{2}}^{v_{1}} \tag{5}\]  
Every alignment \(G\) defines unique mappings \(\pi_{1}(G)\) and \(\pi_{2}(G)\), but the converse is not true. The minimum cost alignment is in general more costly than the minimum cost edit script. We will need a bit of notation. Let \(F\) be an ordered forest. By \(i:F\) we denote the subforest consisting of the first \(i\) trees, while \(F:j\) denotes the subforest starting with the \(j+1\)-st tree. By \(F^{\downarrow}\) we denote the forest consisting of the children-trees of the root \(v=r_{F}\) of the first tree in \(F\). \(F^{\rightarrow}=F:1\) is the forest of the right sibling trees of \(F\). Now consider an alignment \(A\) of two forests \(F_{1}\) and \(F_{2}\). Let \(a=r_{A}\) be the root of its first tree. We have either:  
Figure 3: Alignment of two forests \(F_{1}\) and \(F_{2}\) (**top**) and a sequence of edit operations (relabel, delete, insert) in order to transform \(F_{1}\) into \(F_{2}\) (**below**). Tree alignment conserves the structures of both original trees that can be recovered using the mapping \(\pi_{1}\) or \(\pi_{2}\), respectively. For more details, see Section 6. 1. \(a=(v_{1},v_{2})\). Then \(v_{1}=r_{F_{1}}\) and \(v_{2}=r_{F_{2}}\); \(A^{\downarrow}\) is an alignment of \(F_{1}^{\downarrow}\) and \(F_{2}^{\downarrow}\); \(A^{\rightarrow}\) is an alignment of \(F_{1}^{\rightarrow}\) and \(F_{2}^{\rightarrow}\). 2. \(a=(v_{1},-)\). Then \(v_{1}=r_{F_{1}}\); for some \(k\), \(A^{\downarrow}\) is an alignment of \(F_{1}^{\downarrow}\) and \(k:F_{2}\), and \(A^{\rightarrow}\) is an alignment of \(F_{1}^{\rightarrow}\) with \(F_{2}:k\). 3. \(a=(-,v_{2})\). Then \(v_{2}=r_{F_{2}}\); for some \(k\), \(A^{\downarrow}\) is an alignment of \(k:F_{1}\) and \(F_{2}^{\downarrow}\) and \(A^{\rightarrow}\) is an alignment of \(F_{1}:k\) with \(F_{2}^{\rightarrow}\). These three cases imply the following dynamic programming recursion:  
\[S(F_{1},F_{2})=\min