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.
background image
university bielefeld AG PI BiBiServ
ambient picture