Explaining and controlling ambiguity in dynamic programming

Giegerich R (2000)
In: COMBINATORIAL PATTERN MATCHING. 1848. SPRINGER-VERLAG BERLIN: 46-59.

Conference Paper | Published | English

No fulltext has been uploaded

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
ISSN
PUB-ID

Cite this

Giegerich R. Explaining and controlling ambiguity in dynamic programming. In: COMBINATORIAL PATTERN MATCHING. Vol 1848. SPRINGER-VERLAG BERLIN; 2000: 46-59.
Giegerich, R. (2000). Explaining and controlling ambiguity in dynamic programming. COMBINATORIAL PATTERN MATCHING, 1848, 46-59.
Giegerich, R. (2000). “Explaining and controlling ambiguity in dynamic programming” in COMBINATORIAL PATTERN MATCHING, vol. 1848, (SPRINGER-VERLAG BERLIN), 46-59.
Giegerich, R., 2000. Explaining and controlling ambiguity in dynamic programming. In COMBINATORIAL PATTERN MATCHING. no.1848 SPRINGER-VERLAG BERLIN, pp. 46-59.
R. Giegerich, “Explaining and controlling ambiguity in dynamic programming”, COMBINATORIAL PATTERN MATCHING, vol. 1848, SPRINGER-VERLAG BERLIN, 2000, pp.46-59.
Giegerich, R.: Explaining and controlling ambiguity in dynamic programming. COMBINATORIAL PATTERN MATCHING. 1848, p. 46-59. SPRINGER-VERLAG BERLIN (2000).
Giegerich, Robert. “Explaining and controlling ambiguity in dynamic programming”. COMBINATORIAL PATTERN MATCHING. SPRINGER-VERLAG BERLIN, 2000.Vol. 1848. 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