Parallel dynamic programming and automata theory
Following Karp's discrete Dynamic Programming (DP) approach, this work extends the sequential model for monadic DP to the parallel case. We propose general parallel DP algorithms for pipeline and ring networks. The study of the optimality of these algorithms leads us to the introduction of new classes of multistage automata. However, the important class of Polyadic Dynamic Problems is out of the scope of this theory. Based on the concept of tree automaton, a new theory covering both Sequential and Parallel Dynamic Programming Polyadic Programs is presented. Monadic Programs appear as a particular case of this new theory. A large number of experiments have proved that the schemes proposed in this work lead to efficient implementations.
dynamic programming automata theory pipeline parallelism tree automata