# Algebraic Dynamic Programming on Trees
## 2 Algebraic Dynamic Programming (ADP)  
Algebraic dynamic programming (ADP)[18; 25] is designed around the idea of higher order programming and starts from the realization that a dynamic programming algorithm can be separated into four parts: (i) grammar, (ii) algebra, (iii) signature, and (iv) memoization. These four components are devised and written separately and combined to form possible solutions. One advantage of ADP is that the decoupling of the individual components makes each individual component much easier to design and implement. Another advantage is that different components can be re-used easily. This is in particular true for the grammar, which defines the search space. Hence, it needs to be specified only once. The grammar only specifies the input alphabet and the production rules on how to split the input data structure in subparts. The algebra specifies the cost function and the selection criterion, also called objective function, and thus defines formally what is considered as an \"optimal\" solution. Based on the objective function, the optimal solution is selected from the possible solutions. The scope of the evaluation algebra is quite broad. It can be used e.g., to count and list prioritized (sub-)optimal solutions. The signature is used as a connecting element between grammar and algebra such that they can be re-used and exchanged independently from each other as long as they fit to the signature. In order to recursively use subsolutions to the problem, they are stored using a data structure easy to save and look-up the subsolution to the current instance. This is called memoization. In this section, the four parts of ADP will be explained using string alignment as an example. Before we delve into dynamic programming on trees and forests, we recapitulate the notations for the case of dynamic programming on strings. The problem instance is the venerable Needleman-Wunsch[26] string alignment algorithm. The algorithm expects two strings as input. When run, it produces a score based on the number of matches, mismatches, deletions, and insertions that are needed to rewrite the first into the second input string. One normally assigns a positive score to a match, and negative scores to mismatches, deletions, and insertions. With the separation of concerns provided by algebraic dynamic programming, the algebra that encodes this scoring becomes almost trivial, while the logic of the algorithm, or the encoding of the search space of all possible alignments in the form of a grammar, is the main problem. As such, we mostly concentrate on the grammars, delegating scoring algebras to a secondary place. A simple version of the Needleman-Wunsch algorithm[26] is given by:  
\[ \begin{pmatrix}X\\ X\end{pmatrix} \rightarrow\underbrace{\left( \begin{matrix}X\\ A\end{matrix} \right) \begin{matrix}a\\ a\end{matrix} }_{\text{match}}\mid\underbrace{\left( \begin{matrix}X\\ X\end{matrix} \right) \begin{matrix}a\\ a\end{matrix} }_{\text{deletion}}\mid\underbrace{\left( \begin{matrix}X\\ X\end{matrix} \right) \begin{matrix}-\\ a\end{matrix} }_{\text{insertion}}\mid\underbrace{\left( \begin{matrix} \mathbf{s}\\ \mathbf{s}\\ \mathbf{s}\end{matrix} \right)}_{\text{empty}} \tag{1}\]  
The grammar has one 2-line symbol on the left-hand side, the non-terminal \(\left( \begin{matrix}X\\ X\end{matrix} \right)\). The notion of two lines of \(X\) is indicative of the algorithm requiring two input sequences. This notion will be made more formal in the next section. Here, \(X\) is a non-terminal of the grammar, \(a\) a terminal character, \(\mathbf{\upxi}\) the termination symbol and '\(-\)' the \"no input read\"-symbol. Non-terminals such as \(\left( \begin{matrix}X\\ X\end{matrix} \right)\) are always regarded as one symbol, and can be replaced by any of the rules on the right-hand side that have said symbol on the left-hand side. Terminals, say \(\left( \begin{matrix}-\\ a\end{matrix} \right)\), act on individual inputs, here not moving on the first input, but reading a character \"into\" \(a\) on the second input.