# Algebraic Dynamic Programming on Trees
## 3 DP Algorithms on Trees and Forests
Furthermore, let \(F\) be the ordered forest of trees \(T_{1},\ldots,T_{n}\), where the order is given by assuming a global root node \(r_{0}\), of which \(r_{1},\ldots,r_{n}\) are the direct, ordered children. Labels are associated with both leaves and inner nodes of the tree or forest._We now define the set of operations that will lead to dynamic programming operations on ordered trees and forests. Each operation transforms a tree or forest on the left-hand side of a rule (\(\rightarrow\)) into one or two elements on the right-hand side of a rule. Rules can fail. If a rule fails, it does not produce a result on the right-hand side. In an implementation, right-hand sides typically yield sets or lists of results, where a failure of a rule naturally leads to an empty set or an empty list. **Definition 2** (empty tree or forest). : _If \(T\) is empty, then the rule \(T\rightarrow\epsilon\) yields \(\epsilon\). If \(F\) is empty, then the rule \(F\to e\) yields \(\epsilon\)._  
**Definition 3** (single root). : _If \(T\) with root \(r\) contains just the root \(r\), then \(T\to r\) yields \(r\)._  
**Definition 4** (root separation). : _Given non-empty \(T\), the rule \(T\to r\cdot F\) yields the root \(r\) of \(T\), as well as the ordered forest \(F=T_{r,1}\ldots T_{r,n}\) of trees. Each \(T_{r,k}\) is uniquely defined as the \(k\)'th child of the root \(r\) of \(T\). \(T\to F\cdot r\) is isomorphic to this rule._  
**Definition 5** (leaf separation). : _Given non-empty \(T\), the left-most leaf \(l=\text{leaf}(T)\) that is defined as the leaf the can be reached by following the unique path from the root \(r\) of \(T\) via each left-most child until a leaf has been reached. We write \(T^{\prime}=T-l\) for the tree obtained from \(T\) by deleting the leaf \(l\) and its incident edge. The rule \(T\to l\cdot T^{\prime}\) breaks up \(T\) into the leaf \(l\) and the remaining tree \(T^{\prime}=T-l\). The rule \(T\rightarrow\text{T}\cdot\text{s}\) likewise extracts the right-most leaf._  
**Definition 6** (forest root separation). : _Let \(F=[T_{1},...,T_{k}]\) be non-empty forest \(F=[T_{1},...,T_{k}]\) and let \(r\) be the root of \(T_{k}\), the right-most tree in \(F\). The rule \(F\to F\cdot r\) separates the right-most root, that is, the resulting forest \(F=[T_{1},...,T_{k-1},T_{c1},...,T_{cm}]\) replaces \(T_{k}\) in the the original forest by the child-trees \(T_{c1},...,T_{cm}\) of \(r\). The rule \(F\to r\cdot F\) analogously separates the left-most root \(r\) by replacing the the leftmost tree of \(F\) by the child-trees of its root._  
Definition 4 is a special case where the forest only consists of one tree. **Definition 7** (forest separation). : _The rule \(F\to T\circ F^{\prime}\) separates the non-empty forest \(F\) into the left-most tree \(T\), and the remaining forest \(F^{\prime}\). \(T\) is uniquely defined by the ordering of \(F\). The rule \(F\to F^{\prime}\circ T\) likewise yields the right-most tree._  
The following lemma gives that both tree and forest decomposition are well defined and always lead to a decomposition using at least one of the definitions above. **Lemma 1** (tree decomposition). : _Given any (empty or non-empty) tree \(T\), at least one of the rules Definitions 2-5 yields a decomposition of the tree, where either \(T\) is decomposed into \"atomic\" elements (\(e\) or a single node), or into two parts, each with fewer vertices than \(T\)._  
Proof. : Every tree \(T\) is either empty (Definition 2), contains just one node which then is the root (Definition 3), or contains one or more nodes (Definitions 4 and 5), of which one is separated from the remainder of the structure. **Lemma 2** (forest decomposition). : _For every forest \(F\) the operations Definitions 2, 6 and 7 yield a decomposition._  
Proof. : The argument is analogously to the case of trees. The forest root separation cases given in Definition 6 remove the left- or right-most root from the forest, hence they constitute a decompostion of the structure.