𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallel dynamic programming and automata theory

✍ Scribed by D.G. Morales; F. Almeida; C. Rodrı́guez; J.L. Roda; I. Coloma; A. Delgado

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
307 KB
Volume
26
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

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 ecient implementations.

📜 SIMILAR VOLUMES

From the theory to the tools: parallel d
From the theory to the tools: parallel dynamic programming
✍ Gonz�lez, D.; Almeida, F.; Roda, J.; Rodr�guez, C. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

Dynamic programming is an important paradigm that has been widely used to solve problems in various areas such as control theory, operation research, biology and computer science. We generalize the finite automaton formal model for dynamic programming deriving pipeline parallel algorithms. The optim