# Algebraic Dynamic Programming on Trees
## 9 Tree Editing  
The string-to-string correction problem can be generalized to forests. To this end, edit operations need to be explained for trees. We consider substitution, insertion, and deletion:  
\[\tikzfig{height=1.5 pt, width=1.5 pt} \tag{13}\]  
and associate them with costs \(\gamma_{y}^{x}\), \(\gamma_{z}^{\varnothing}\), or \(\gamma_{\varnothing}^{z}\). In this section, we explain our formal grammar for the string editing algorithm on trees instead of strings. Comparing and editing strings is a well-known algorithm in computer science applications, and hence, we expanded this application to trees as input described by a formal grammar. Our grammar is based on [8] which shows one possible solution for the tree editing DP algorithm. There exist other ways which try to minimize the search space of possible solutions by explicitly choosing where to start the next iteration step [31; 47; 48]. **Definition 11** (Tree editing). : _A mapping [49] between two ordered forests \(F_{1}\) to \(F_{2}\) is a binary relation \(M\in V(F_{1})\times V(F_{2})\) between the vertex sets of the two forests such that for pairs \((x,y)\), \((x^{\prime},y^{\prime})\in M\) holds_  
1. \(x=x^{\prime}\) _if and only if_ \(y=y^{\prime}\)_. (one-to-one condition)_
2. \(x\) _is an ancestor of_ \(x^{\prime}\) _if and only if_ \(y\) _is an ancestor of_ \(y^{\prime}\)_. (ancestor condition)_
3. \(x\) _is to the left of_ \(x^{\prime}\) _if and only if_ \(y\) _is to the left of_ \(y^{\prime}\)_. (sibling condition)_  
The one-to-one condition implies that for each \(x\in F_{1}\) there is a unique \"partner\" \(y\in F_{2}\), i.e., \((x,y)\in M\), or \(x\) has no matching partner at all. With each mapping we can associate the cost  
\[\gamma(M)=\sum_{(x,y)\in M}\gamma_{y}^{x}+\sum_{y:(x,y)\
otin M}\gamma_{y}^{ \varnothing}+\sum_{x:(x,y)\
otin M}\gamma_{\varnothing}^{x} \tag{14}\]  
Individual edit operations correspond to \"elementary maps\". Maps can be composed in a natural manner. Thus every edit script corresponds to a map. Conversely every map can be composed of elementary maps, and thus corresponds to an edit script. Furthermore, the cost of maps is subadditive under composition. As a consequence, minimum cost mappings are equivalent to the minimum cost edit scripts [32]. The problem of minimizing \(\gamma(M)\) has a dynamic programming solution. For a given forest \(F\) and a root node \(v\) in \(F\), we denote by \(F-v\) the forest obtained by deleting \(v\) and \(F\setminus T(v)\) is the forest obtained from \(F\) by deleting with \(v\) all descendants of \(v\). Note that \(T(v)-v\) is the forest consisting of all trees whose roots are the children of \(v\). Equation (15) shows the recursion equations. \[D(F_{1},F_{2})=\min \begin{cases}D(F_{1}-v_{1},F_{2})+\gamma_{\varnothing}^{v_ {1}}\\ D(F_{1},F_{2}-v_{2})+\gamma_{\varnothing}^{v_{2}}\\ D(T(v_{1})-v_{1},T(v_{2})-v_{2})+\gamma_{\varnothing}^{v_{1}}\\ \qquad+D(F_{1}-T(v_{1}),F_{2}-T(v_{2}))\end{cases}  \tag{15}\]  
with \(D(\emptyset,\emptyset)=0\) for two empty forests. A key issue is to implement this algorithm in such a way that only certain classes of subforests need to be evaluated. Our grammar is based on the algorithm described in [8]. Here, forests are decomposed into the right-most tree and the remaining forest, whichis not specified in the recursion equations in Equation (15). The corresponding tree editing grammar \(\mathcal{E}\) reads  
\[ \begin{pmatrix}T\\ T\end{pmatrix} \ \rightarrow\ \begin{pmatrix}F\\ F\end{pmatrix} \downarrow \begin{pmatrix}n\\ n\\ n\end{pmatrix}  \tag{16}\] \[ \begin{pmatrix}F\\ F\end{pmatrix} \ \rightarrow\ \begin{pmatrix}F\\ F\end{pmatrix} \circ \begin{pmatrix}T\\ T\end{pmatrix} \ \ \big{|}\ \begin{pmatrix}F\\ F\end{pmatrix} \downarrow \begin{pmatrix}x\\ -\end{pmatrix} \ \big{|}\ \begin{pmatrix}F\\ F\end{pmatrix} \downarrow \begin{pmatrix}-\\ x\end{pmatrix} \ \big{|}\ \begin{pmatrix}\xi\\ \xi\end{pmatrix} \]  
Note that the empty symbol \"\(-\)\" acts as neutral element for the concatenation operators, which we take to act component-wise.