# Algebraic Dynamic Programming on Trees
## 6 Tree Alignment
(ii) The set of deleted nodes form a simple surjection from a node \(a\in T_{i}\) onto a symbol (typically '-') indicating no partner. (iii) For trees \(T_{j}\), (ii) holds analogously._  
The problem descriptions in Definitions 9 and 10 are equivalent. Every forest can be defined as a tree with the roots of the forest as children of a trees' root. Given Definition 9, the mappings \(\pi_{1}\) and \(\pi_{2}\) can therefore be applied to a tree as well. Given Definition 10 (i), the partial order is also preserved in case of forests, as the roots of the forests are partially ordered, too. Definition 10 (ii) and (iii) define the order of the deleted nodes that is preserved within the tree. This is also true for forests, and obtained by the mappings \(\pi_{1}\) and \(\pi_{2}\) defined in Definition 9. A multiple alignment of forest structures can be constructed given the Definitions 2-7 and Lemmas 1 and 2 We now show that, given these definitions, the alignment is well-defined and can always be constructed independent of the input structures. We _do not_ show here that the resulting alignment is optimal in some sense, as this depends on the optimization function (or algebra) used. Let \((F_{1},\ldots,F_{k})\) be an input of \(k\) forests. Successive, independent application of the operations specified in Definitions 2-7 and Lemmas 1 and 2 to individual input trees yields the multi-tape version of the empty string \((\epsilon_{1},\ldots,\epsilon_{k})\), i.e., the input is reduced to empty structures. Not every order of application necessarily yields an alignment. Just as in the case of sequence alignments [17] the allowed set of operations needs to be defined for multi-tape input. This amounts in particular to specify which operations act concurrently on multiple tapes. The above-given definitions can be subdivided into two sets. One set of operations takes a forest \(F\) and splits off the left- or right-most tree (\(F\to F^{\prime}T\) or \(F\to TF^{\prime}\)), where both \(F^{\prime}\) and \(T\) are allowed to be empty. In case of \(T\) being empty then it holds that \(F^{\prime}=F\). If \(F^{\prime}\) is empty, then this yields a decomposition of \(F\) only if \(F\) consists of just a single tree. The other set of operations removes atomic elements from a tree and yields a tree or forest, depending on the rule used. As in [17], all operations have to operate in \"type lockstep\" on all inputs simultaneously. That is, either all inputs separate off the left- or right-most tree and yield the trees \((T_{1},\ldots,T_{k})\) and remaining forests \((F_{1},\ldots,F_{k})\), or all operations remove a terminal or atomic element, yielding the terminal elements \((n_{1},\ldots,n_{k})\) and remaining structure \((S_{1},\ldots,S_{k})\). Furthermore, an operation \(T\to T^{\prime}-^{\prime}\) is introduced. This operation does not further decompose \(T\) but provides a terminal symbol \({}^{\prime}-^{\prime}\) as element \(n_{i}\). This is analogous to the in/del case in string alignments. **Theorem 1** (Alignment). : _Every input \((F_{1},\ldots,F_{k})\) of forests can be reconstructed into \((\epsilon_{1},\ldots,\epsilon_{k})\) by successive application of the steps outlined above._  
Proof of Theorem 1.: At least one of the decompositions defined above for forests (Definitions 2, 6 and 7) or trees (Definitions 2-5) can always be applied for each input. Due to lockstep handling, all inputs simultaneously separate into a tree and remaining forest (yielding two structures), or apply a rule yielding a terminal element. As such, either all structures are already empty (\(=\epsilon\)) or at least one structure can be further decomposed yielding a smaller structure.