# Algebraic Dynamic Programming on Trees
## 3 DP Algorithms on Trees and Forests  
Algebraic dynamic programming [25] in its original form was designed for single-sequence problems. Alignment-style problems were solved by concatenating the two inputs and including a separator. Originally, ADPfusion[18] was designed along the lines of ADP, but gained provisions to abstract over both the input type(s), and the index space with the advent of generalized algebraic dynamic programming [17; 24; 27; 28; 29] inputs were generalized to strings and sets, as well as multiple tapes (or inputs) of those. Trees as data structures sit \"somehow between\" strings and sets. They have more complex structures, in that each node not only has siblings, but also children compared to lists which only have siblings for each node in the list or string. Sets on the other hand are typically used based on the principle of having edges between all nodes, with each edge having a particular weight. This alone makes trees an interesting structure to design a formal dynamic programming environment for. Tree and forest structures have, as discussed above, important functions in (for example) bioinformatics and linguistics. DP algorithms can be applied not only to just one input structure but also to two or more independent inputs. In the context of formal grammars describing DP algorithms we denote DP algorithms applied to one input structure as single-tape and two or more inputs as two-tape or multi-tape algorithms in analogy to the terminology used in the theory of automata in theoretical computer science. Mixing tapes, i.e., having a tree on one tape and a string on the other is possible. Due to the splitting of grammar, signature, algebra and memoization, the underlying machinery is presented with an index structure to traverse that corresponds to the decomposition rules of the data structure(s). Hence, during one iteration step it is possible that the algorithm consumes one character of the input string on one tape whereas the second tape recurses on a tree. We now formalize the notion of an input tape on which formal grammars act. For sequences, an input tape is a data type that holds a finite number of ordered elements. The ordering is one-dimensional. It provides the ability to address each element. For all algorithms considered here, the input tape is immutable. Sequences are the focus of earlier work [17; 18]. Input tapes on _trees_ hold a finite number of elements with a parent-child-sibling relationship. Each element has a single parent or is a root element. Each element has between zero and many children. The children are ordered. For each child, its left and right sibling can be defined, unless the child is the left-most or right-most child. Input tapes on _forests_ introduce a total order between the root elements of the trees forming the forest. These structures are discussed in this work. For sets, the tape structure is the power set and the partial order defined by subset inclusion. Set structures have been discussed earlier [24]. A multi-tape grammar, such as the example above, extends this notion to tuples of input tapes. We will formalize the notion of multi-tape inputs later in Definition 8. We note in passing that in the case of multiple context-free grammars the one-to-one correspondence between the \(i\)'th element of the tuple and the \(i\)'th row of each rule does not hold for interleaved symbols. We refer to [29] for the details. In order to define formal grammars for DP algorithms on trees and forests, we have to define how to split a tree or a forest into its substructures. On strings, the concatenation operator is assumed implicitly to concatenate single symbols of the string. We make the operators explicit as there is more than one operator on trees and forests. **Definition 1** (trees and forests). : _Let \(T\) be a rooted, ordered tree. Then, either \(T\) is empty and contains no nodes, or there is a designated node \(r\), the root of the tree. In addition, for each non-leaf node, there is a given order of its children from left to right.