# Introduction

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

## Examples

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