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

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

Download
OA
Bielefeld Dissertation | English
Supervisor
Giegerich, Robert
Abstract
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.
Year
PUB-ID

Cite this

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.
Main File(s)
File Name
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Search this title in

Google Scholar