Gnesi S., Martelli A., Montanari U. Dynamic programming as graph searching: an algebraic approach. Gia' apparsa come nota interna s79-26 dell'Istituto di Scienze della Informazione, Pisa. Giugno 1979. Internal note IEI-B79-16, 1979. |

Abstract (English) |
Finding the solution of a dynamic programming problem in polyadic functional equations is shown to be equivalent to searching a minimal cost path in an AND/OR graph. The proof is given in an algebraic framework, and it is based on a commutativity result between solution and interpretation of a symbolic system. This approach is similar to the one used by some authors to prove the equivalence between the operational and denotational semantics of programming languages. | |

Subject | dynamic programming functional equations AND/OR graph graph search continuous algebras algebraic semantics |

1) Download Document PDF |

Open access Restricted Private