# Algebraic Dynamic Programming on Trees
## 1 Introduction  
Dynamic programming (DP) is a general paradigm for solving combinatorial problems with a search space of exponential size in polynomial time (and space). The key idea is that the optimal solution for the overall problem can be constructed by combining the optimal solutions to subproblems (known as optimal substructure). During the recursive deconstruction of the original problem instance, the same smaller subproblems (known as overlapping subproblems) are required repeatedly and thus memoized. DP is typically applied to optimization and (weighted) enumeration problems. Not all such problems are amenable to this strategy however. _[PERSON]'s principle_[1] codifies the key necessary condition, the intuition of which can be expressed for optimization problems as follows: The optimal solution of any (sub)problem can be obtained as a suitable combination of optimal solutions of its subproblems. In Bioinformatics, DP algorithms are a useful tool to solve tasks such as sequence alignment [2] or RNA secondary structure prediction [3, 4]. Here, the description of dynamic programming algorithms as formal grammars is common practice [5]. Problems whose natural input structure is a tree typically have no satisfactory solution using an encoding as strings, because one \"dimension\" within the input islost. As a consequence, solutions to seemingly similar string problems can be very different. A simple example is comparison of two patterns of matching parentheses:  
(((((((()))))))) ((((((()))))))--)  (((((()))))) ((((((-)))))))  
On the l.h.s., they are interpreted as strings differing by two substitutions. On the r.h.s., interpreted as trees the difference is the insertion and deletion of matching pairs in each pattern. A simple, yet often encountered, example of a tree is the structure of a text such as a book. Books are divided into chapters, sections, subsections, and blocks of text, imposing a hierarchical structure in addition to the linear order of words. Many other formats for data exchange are based on similar structures, including json and xml. In bioinformatics, tree structures encode, among others, the (secondary) structure of RNA and phylogenetic trees, hence DP algorithms on trees have a long history in computational biology. Well-studied problems include the computation of parsimony and likelihood scores for given phylogenies [6], tree alignment [7] and tree editing [8], reconciliation of phylogenetic trees [9], and RNA secondary structure comparison [10; 11]. [PERSON] and [PERSON] [12] developed a system of inverse coupled rewrite systems (ICOREs) which unify dynamic programming on sequences and trees. Rules written in this system bear a certain semblance to our system. We are not aware of an implementation of ICORES, however, making comparisons beyond the formalism difficult. All of these approaches use trees and/or forests as input structures. Aims and methods, however, are different. We argue here that a common high-level framework will substantially simplify the design and development of such algorithms and thus provide a very useful addition to the toolbox of someone working with tree-like data. There are implementations for most of the problems mentioned above. However, they use problem-specific choices for the recursions and memoization tables that seem to be hard to generalize. A particularly difficult challenge is the construction of DP algorithms that are not only complete but also semantically unambiguous. The latter property ensures that each configuration is considered only once, so that the DP recursion correctly counts and thus can be used to compute partition functions. A recent example is the approach of [7] to tree alignment. In general, recognizing ambiguity for context-free grammars is undecidable [13; 14]. There are, however, quite efficient heuristics that can be used successfully to prove that string grammars describing many problems in computational biology are unambiguous [15].