Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Algebraic dynamic programming for multiple context-free grammars

: Riechert, M.; Höner zu Siederdissen, C.; Stadler, P.F.


Theoretical computer science 639 (2016), pp.91-109
ISSN: 0304-3975
Journal Article
Fraunhofer IZI ()

We present theoretical foundations, and a practical implementation, that makes the method of Algebraic Dynamic Programming available for Multiple Context-Free Grammars. This allows to formulate optimization problems, where the search space can be described by such grammars, in a concise manner and solutions may be obtained efficiently. This improves on the previous state of the art which required complex code based on hand-written dynamic programming recursions. We apply our method to the RNA pseudoknotted secondary structure prediction problem from computational biology.Appendix and supporting files available at: