2:00 p.m.

Classified Dynamic Programming with Product Algebras

Robert Giegerich, Bielefeld

Classified dynamic programming is a technique to refine analyses implemented by dynamic programming, in the best case without changing tried-and-tested code. It has certainly been discovered many times as an ad-hoc trick. But also, examples abound where it should have been applied, but programmers chose a much more tedious route of implementation. In the terminilogy of algebraic dynamic programming, classified DP simply means the use of a product algebra C*A, where C computes a classification attribute and A is an arbitrary scoring scheme. The presentation introduces classified DP in ADP style, relates efficiency to the cardinality of the classification range, and discusses applications in semantic ambiguity checking and compensation.

3:00 p.m.

A Weighted Deductive Language for Declaratively Specifying (Some) Algorithms

Jason Eisner, JHU

Building intelligent or interactive systems has become increasingly challenging as our ambitions scale up. The Dyna programming language (under development) attempts to capture the shared design patterns that are reused across these systems. It enables declarative specification backed by general algorithms and data structures. It may be regarded as a kind of deductive database, theorem prover, truth maintenance system, or equation solver. It tightly integrates logic programming with functional programming, and also supports modularity. I will illustrate how Dyna makes it easy to specify the abstract structure of various kinds of computations, including typical AI computations (usually described as dynamic programming, message passing, propagation, or feed-forward). I will then sketch the space of execution strategies that can efficiently answer queries and propagate updates. Finally, I will suggest that machine learning should be used to search for the best execution strategies for a particular program on a particular workload.

4:00 p.m.

Break

4:15 p.m.

Compiling Adventures in Bellman's GAP

Georg Sauthoff, Bielefeld University

Algebraic Dynamic Programming (ADP) is a declarative style of dynamic programming, which has emerged in the area of biosequence analysis. Based on the concepts of signatures, algebras, and regular tree grammars, a dynamic programming algorithm can be expressed at a convenient level of abstraction, obviating the development and the tedious debugging of the matrix recurrences typical of dynamic programming. The ADP method has been used in implementing a good number of bioinformatics tools in the area of RNA structure prediction. Bellman's GAP is a new domain specific language for writing programs in the ADP paradigm. Bellman's GAP contains C/Java-like syntax elements and a notation for tree grammars resembling function calls. Compiling the declarative source code essentially means the derivation of and code generation for efficient dynamic programming recurrences. The current compiler implements non-trivial semantic analyses like yield-size analysis and table design. Further examples are the automatic generation of different backtracing schemes or the generation of OpenMP-parallelized code. The talk will give an introduction to the challenges of compiling ADP. It will discuss type-checking, semantic analyses and code-generation, including optimization by the compiler which lead to implementations competitive with handwritten code.