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
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Konferenzbeitrag | Veröffentlicht | Englisch
Herausgeber
;
Abstract / Bemerkung
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.
Erscheinungsjahr
Titel des Konferenzbandes
Combinatorial Pattern Matching. 11th Annual Symposium CPM 2000, Proceedings
Band
1848
Seite
46-59
Konferenz
CPM 2000
Konferenzort
Montréal, Canada
Konferenzdatum
2000-06-21 – 2000-06-23
PUB-ID

Zitieren

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.