Dynamic Programming as Graph Searching: An Algebraic Approach

DOI10.1145/322276.322285zbMath0471.90092OpenAlexW2078945336MaRDI QIDQ3926375

Stefania Gnesi, Alberto Martelli, Ugo Montanari

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322276.322285

zbMATH Keywords

functional equationsalgebraic semanticsgraph searchalgebraic approachcontinuous algebrassemantics of programming languagessymbolic systemminimal cost pathAND/OR graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39) Programming in abstract spaces (90C48) Semantics in the theory of computing (68Q55)

Related Items (13)

Systolic processing for dynamic programming problems ⋮ A general heuristic bottom-up procedure for searching AND/OR graphs ⋮ Contributions to a computational theory of policy advice and avoidability ⋮ Dynamic maintenance of the transitive closure in disjunctive graphs ⋮ A general framework for enumerating equivalence classes of solutions ⋮ Dynamic maintenance of directed hypergraphs ⋮ Computing the throughput of concatenation state machines ⋮ The weighted list update problem and the lazy adversary ⋮ Partially dynamic maintenance of minimum weight hyperpaths ⋮ Directed hypergraphs and applications ⋮ The Why, How, and When of Representations for Complex Systems ⋮ A Comprehensive Model of Dynamic Programming ⋮ Extensional equality preservation and verified generic programming

This page was built for publication: Dynamic Programming as Graph Searching: An Algebraic Approach