A discipline of dynamic programming over sequence data

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

Journal Article | Published | English

No fulltext has been uploaded

Abstract
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.
Publishing Year
ISSN
PUB-ID

Cite this

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.
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.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar