Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming

Sauthoff G (2010)
Bielefeld (Germany): Bielefeld University.

Bielefelder E-Dissertation | Englisch
 
Download
OA
Betreuer*in
Giegerich, Robert
Abstract / Bemerkung
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.
Stichworte
Regular Tree Grammars; RNA Structure Prediction; Table Design; Dynamic Programming; Formale Grammatik; Optimierender Compiler; Domänenspezifische Programmiersprache; Dynamische Optimierung
Jahr
2010
Page URI
https://pub.uni-bielefeld.de/record/2304195

Zitieren

Sauthoff G. Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming. Bielefeld (Germany): Bielefeld University; 2010.
Sauthoff, G. (2010). Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming. Bielefeld (Germany): Bielefeld University.
Sauthoff, G. (2010). Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming. Bielefeld (Germany): Bielefeld University.
Sauthoff, G., 2010. Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming, Bielefeld (Germany): Bielefeld University.
G. Sauthoff, Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming, Bielefeld (Germany): Bielefeld University, 2010.
Sauthoff, G.: Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming. Bielefeld University, Bielefeld (Germany) (2010).
Sauthoff, Georg. Bellman's GAP : a 2nd generation language and system for algebraic dynamic programming. Bielefeld (Germany): Bielefeld University, 2010.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T08:57:45Z
MD5 Prüfsumme
901731d5e80065ecf5090b180b2b5012

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar