Explaining and controlling ambiguity in dynamic programming

Giegerich R (2000)
In: Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings. Giancarlo R, Sankoff D (Eds); Lecture Notes in Computer Science, 1848. Berlin: Springer: 46-59.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published | English

No fulltext has been uploaded

Editor
Giancarlo, Raffaele ; Sankoff, David
Abstract
Ambiguity in dynamic programming arises from two independent sources, the non-uniqueness of optimal solutions and the particular recursion scheme by which the search space is evaluated. Ambiguity, unless explicitly considered, leads to unnecessarily complicated, inflexible, and sometimes even incorrect dynamic programming algorithms. Building upon the recently developed algebraic approach to dynamic programming, we formalize the notions of ambiguity and canonicity. We argue that the use of canonical yield grammars leads to transparent and versatile dynamic programming algorithms. They provide a master copy of recurrences, that can solve all DP problems in a well-defined domain. We demonstrate the advantages of such a systematic approach using problems from the areas of RNA folding and pairwise sequence comparison.
Publishing Year
Conference
CPM 2000
Location
Montréal, Canada
Conference Date
2000-06-21 – 2000-06-23
PUB-ID

Cite this

Giegerich R. Explaining and controlling ambiguity in dynamic programming. In: Giancarlo R, Sankoff D, eds. Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings. Lecture Notes in Computer Science. Vol 1848. Berlin: Springer; 2000: 46-59.
Giegerich, R. (2000). Explaining and controlling ambiguity in dynamic programming. In R. Giancarlo & D. Sankoff (Eds.), Lecture Notes in Computer Science: Vol. 1848. Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings (pp. 46-59). Berlin: Springer.
Giegerich, R. (2000). “Explaining and controlling ambiguity in dynamic programming” in Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings, Giancarlo, R., and Sankoff, D. eds. Lecture Notes in Computer Science, vol. 1848, (Berlin: Springer), 46-59.
Giegerich, R., 2000. Explaining and controlling ambiguity in dynamic programming. In R. Giancarlo & D. Sankoff, eds. Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings. Lecture Notes in Computer Science. no.1848 Berlin: Springer, pp. 46-59.
R. Giegerich, “Explaining and controlling ambiguity in dynamic programming”, Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings, R. Giancarlo and D. Sankoff, eds., Lecture Notes in Computer Science, vol. 1848, Berlin: Springer, 2000, pp.46-59.
Giegerich, R.: Explaining and controlling ambiguity in dynamic programming. In: Giancarlo, R. and Sankoff, D. (eds.) Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings. Lecture Notes in Computer Science. 1848, p. 46-59. Springer, Berlin (2000).
Giegerich, Robert. “Explaining and controlling ambiguity in dynamic programming”. Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings. Ed. Raffaele Giancarlo and David Sankoff. Berlin: Springer, 2000.Vol. 1848. Lecture Notes in Computer Science. 46-59.
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