TY  - THES
AB  - The dissertation describes the new Bellman’s GAP which is a programming system for writing dynamic programming algorithms over sequential data. It is the second generation implementation of the algebraic dynamic programming framework (ADP). The system includes the multi-paradigm language (GAP-L), its compiler (GAP-C), functional modules (GAP-M) and a web site (GAP Pages) to experiment with GAP-L programs. GAP-L includes declarative constructs, e.g. tree grammars to model the search space, and imperative constructs for programming advanced scoring functions. The syntax of GAP-L is similar to C/Java to lower usage barriers. GAP-C translates the high-level and index-free GAP-L programs into efficient C++-Code, which is competitive with handwritten code. It includes a novel table design optimization algorithm, support for dynamic programming (DP) over multiple sequences (multi-track DP), sampling, optional top-down evaluation, various backtracing schemes etc. GAP-M includes modules for use in GAP-L programs. Examples are efficient representations of classification data types and sampling as well as filter helper functions. GAP Pages contain web dialogs for selected text book dynamic programming algorithms implemented in GAP-L. The web dialogs allow interactive ad-hoc experiments with different inputs and combinations of algebras. Several benchmarks and examples in the dissertation show the practical efficiency of Bellman’s GAP in terms of program runtime and development time.
DA  - 2010
KW  - Regular Tree Grammars
KW  - RNA Structure Prediction
KW  - Table Design
KW  - Dynamic Programming
KW  - Formale Grammatik
KW  - Optimierender Compiler
KW  - Domänenspezifische Programmiersprache
KW  - Dynamische Optimierung
LA  - eng
PY  - 2010
TI  - Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:361-18210
Y2  - 2024-11-22T02:59:49
ER  -