Logic-programming specification and execution of dynamic-programming problems

AbstractDynamic programming has been used since the late 1950s to solve numerical problems that have natural recursive formulations that succumb to divide-and-conquer strategies. However, to improve the efficiency of the divide-and-conquer strategy, conventional methods of dynamic programming use intricate and imperative tabular techniques that are entirely excluded from the purely relational/functional world of logic programming. This is ironic when one considers that dynamic programming is often used for problems that can be specified elegantly in logic, abstracting away from considerations of table storage and access. This paper describes a method by which problems normally solved by dynamic programming can be expressed in Horn clauses, which are then used together with a goal clause to construct dataflow graphs with the same efficient computational properties as a dynamic-programming solution. The method is implemented, and takes the form of a compiler from Horn clauses to dataflow graphs. The method is demonstrated on two typical problems: the series of probabilities and the optimal association of matrix chain products. A class of problems, which includes the integer maximal knapsack problem, is identified to which the method is not applicable