Algebraic dynamic programming for multiple context-free grammars

摘要

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 handwritten dynamic programming recursions. We apply our method to the RNA pseudoknotted secondary structure prediction problem from computational biology.