Bellman's GAP Café
Introduction Applications
Compiler Education Literature FAQ About Contact Impressum


These web pages describe 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).

Bellman's GAP

The system includes the multi-paradigm language (GAP-L), its compiler (GAP-C) and functional modules (GAP-M) . 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.

See also


The application section contains several DP examples implemented in GAP-L and presented as web applications. The examples range from selected text book DP algorithms to RNA secondary structure prediction. Web dialogs allow interactive ad-hoc experiments with different inputs and combinations of algebras.

You can also download the source of the examples and compile them on your computer with the GAP compiler.

Several benchmarks and examples in the dissertation show the practical efficiency of Bellman’s GAP in terms of program runtime and development time.

Algebraic dynamic programming

Algebraic Dynamic Programming (ADP) is a formal framework for specifying dynamic programming algorithms on sequences. It clearly separates the concerns of search space description, candidate description, candidate evaluation and tabulation.

Tree grammars (G) specify the search space, algebras (E) evaluate candidate terms and signatures (Σ) declare the function reservoir which tree grammars and algebras are using. Tabulation is specified through non-terminal annotation in tree grammars. The use of tree grammars for search space description eliminates subscripts from the algorithm description, i.e. a major source of programming errors in developing DP algorithms.

Algebras are building blocks to wrap different scoring schemes or optimization strategies (h). With product operations they can be combined to more powerful analyses.

See also