Dynamic programming for Set data structures.

generalized Algebraic Dynamic Programming

Extensions of ADPfusion for set-(like) data structures.

ADPfusionSet

generalized Algebraic Dynamic Programming Homepage

Ideas implemented here are described in a couple of papers:

1. Christian Hoener zu Siederdissen
   Sneaking Around ConcatMap: Efficient Combinators for Dynamic Programming
   2012, Proceedings of the 17th ACM SIGPLAN international conference on Functional programming
   paperpreprint
2. Andrew Farmer, Christian Höner zu Siederdissen, and Andy Gill.
   The HERMIT in the stream: fusing stream fusion’s concatMap
   2014, Proceedings of the ACM SIGPLAN 2014 workshop on Partial evaluation and program manipulation.
   paper
3. Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.
   Product Grammars for Alignment and Folding
   2014, IEEE/ACM Transactions on Computational Biology and Bioinformatics. 99
   paper
4. Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler
   Algebraic Dynamic Programming over General Data Structures
   2015, BMC Bioinformatics
   preprint
5. Maik Riechert, Christian Höner zu Siederdissen, and Peter F. Stadler
   Algebraic dynamic programming for multiple context-free languages
   2015, submitted
   preprint

Introduction

ADPfusionSet extends ADPfusion with index structures suitable for sets. Included are sets, and sets with one and two boundaries. The classical example for DP on sets with a single boundary is the travelling salesman problem. Here, the set denotes the set of cities already visited, while the boundary is the last city that was visited.

Installation

Follow the gADP examples.

Contact

Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany
[email protected]
http://www.bioinf.uni-leipzig.de/~choener/