Putting it all together

Definition (Algebraic dynamic programming)

- An ADP problem is specified by a signature Σ over Α, a yield grammar (G,y) over Σ, and a Σ-evaluation algebra I with objective function h_I.
- An ADP problem instance is posed by a string w ∈ A*. The search space it spawns is the set of all its parses, P_G(w).
- Solving an ADP problem is computing
h_I{t_I | t ∈ P_G(w)}in polynomial time and space.