Bellman's GAP [Elektronische Ressource] : a 2nd generation language and system for algebraic dynamic programming / Georg Sauthoff. Technische Fakultät - AG Praktische Informatik

Dissertation zur Erlangung des akademischen Gradeseines Doktors der Naturwissenschaften (Dr. rer. nat.)der Technischen Fakultät der Universität BielefeldBellman’s GAP: A 2nd GenerationLanguage and System for AlgebraicDynamic Programming∗Georg SauthoffMarch 4, 2011∗gsauthof@techfak.uni-bielefeld.deGedruckt auf alterungsbeständigem Papier °° ISO 9706AbstractThe dissertation describes the new Bellman’s GAP which is a programming sys-tem for writing dynamic programming algorithms over sequential data. It is thesecond generation implementation of the algebraic dynamic frame-work (ADP) [20]. The system includes the multi-paradigm language (GAP-L), itscompiler (GAP-C), functional modules (GAP-M) and a web site (GAP Pages) toexperimentwithGAP-Lprograms. GAP-Lincludesdeclarativeconstructs, e.g.treegrammars to model the search space, and imperative constructs for programmingadvanced scoring functions. The syntax of GAP-L is similar to C/Java to lowerusage barriers. GAP-C translates the high-level and index-free GAP-L programsinto efficient C++-Code, which is competitive with handwritten code. It includes anovel 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 pro-grams. Examples are efficient representations of classification data types and sam-pling as well as filter helper functions.