Istituto di Scienza e Tecnologie dell'Informazione     
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.
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

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional