A discipline of dynamic programming over sequence data

Giegerich R, Meyer C, Steffen P (2004)
SCIENCE OF COMPUTER PROGRAMMING 51(3): 215-263.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Abstract / Bemerkung
Dynamic programming is a classical programming technique, applicable in a wide variety ofdomains such as stochastic systems analysis, operations research, combinatorics of discrete structures, flow problems, parsing of ambiguous languages, and biosequence analysis. Little methodology has hitherto been available to guide the design of such algorithms. The matrix recurrences that typically describe a dynamic programming algorithm are difficult to construct, error-prone to implement, and, in nontrivial applications, almost impossible to debug completely. This article introduces a discipline designed to alleviate this problem. We describe an algebraic style of dynamic programming over sequence data. We define its formal framework, based on a combination of grammars and algebras, and including a formalization of Bellman's Principle. We suggest a language used for algorithm design on a convenient level of abstraction. We outline three ways of implementing this language, including an embedding in a lazy functional language. The workings of the new method are illustrated by a series of examples drawn from diverse areas of computer science. (C) 2004 Elsevier B.V. All rights reserved.
Erscheinungsjahr
Zeitschriftentitel
SCIENCE OF COMPUTER PROGRAMMING
Band
51
Zeitschriftennummer
3
Seite
215-263
ISSN
PUB-ID

Zitieren

Giegerich R, Meyer C, Steffen P. A discipline of dynamic programming over sequence data. SCIENCE OF COMPUTER PROGRAMMING. 2004;51(3):215-263.
Giegerich, R., Meyer, C., & Steffen, P. (2004). A discipline of dynamic programming over sequence data. SCIENCE OF COMPUTER PROGRAMMING, 51(3), 215-263. doi:10.1016/j.scico.2003.12.005
Giegerich, R., Meyer, C., and Steffen, P. (2004). A discipline of dynamic programming over sequence data. SCIENCE OF COMPUTER PROGRAMMING 51, 215-263.
Giegerich, R., Meyer, C., & Steffen, P., 2004. A discipline of dynamic programming over sequence data. SCIENCE OF COMPUTER PROGRAMMING, 51(3), p 215-263.
R. Giegerich, C. Meyer, and P. Steffen, “A discipline of dynamic programming over sequence data”, SCIENCE OF COMPUTER PROGRAMMING, vol. 51, 2004, pp. 215-263.
Giegerich, R., Meyer, C., Steffen, P.: A discipline of dynamic programming over sequence data. SCIENCE OF COMPUTER PROGRAMMING. 51, 215-263 (2004).
Giegerich, Robert, Meyer, C, and Steffen, Peter. “A discipline of dynamic programming over sequence data”. SCIENCE OF COMPUTER PROGRAMMING 51.3 (2004): 215-263.