Algebraic dynamic programming on trees
Summary: Where string grammars describe how to generate and parse strings, tree grammars describe how to generate and parse trees. We show how to extend generalized algebraic dynamic programming to tree grammars. The resulting dynamic programming algorithms are efficient and provide the complete feature set available to string grammars, including automatic generation of outside parsers and algebra products for efficient backtracking. The complete parsing infrastructure is available as an embedded domain-specific language in Haskell. In addition to the formal framework, we provide implementations for both tree alignment and tree editing. Both algorithms are in active use in, among others, the area of bioinformatics, where optimization problems on trees are of considerable practical importance. This framework and the accompanying algorithms provide a beneficial starting point for developing complex grammars with tree- and forest-based inputs.
- A discipline of dynamic programming over sequence data
- A survey on tree edit distance and related problems
- Algebraic dynamic programming for multiple context-free grammars
- Alignment of trees -- an alternative to tree edit
- Analyzing ambiguity of context-free grammars
- Biological Sequence Analysis
- Call-pattern specialisation for Haskell programs
- Code selection by inversion of order-sorted derivors
- Counting, Generating and Sampling Tree Alignments
- Efficient computation of the tree edit distance
- Forest Alignment with Affine Gaps and Anchors
- scientific article; zbMATH DE number 3361265 (Why is no real title available?)
- Minimal Mutation Trees of Sequences
- Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
- New algorithm for ordered tree-to-tree correction problem
- On The Ambiguity Problem of Backus Systems
- On the Theory of Dynamic Programming
- Regular, shape-polymorphic, parallel arrays in Haskell
- RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
- Segmental mapping and distance for rooted labeled ordered trees
- Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
- Sneaking around concatmap, efficient combinators for dynamic programming
- The Tree-to-Tree Correction Problem
- The tree-to-tree editing problem
- Tree edit distance cannot be computed in strongly subcubic time (unless APSP can)
- Tree generating regular systems
- Computing abstract decorations of parse forests using dynamic programming and algebraic power series
- Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
- Compositional properties of alignments
- Algebraic dynamic programming
- Algebraic dynamic programming for multiple context-free grammars
- scientific article; zbMATH DE number 2090016 (Why is no real title available?)
This page was built for publication: Algebraic dynamic programming on trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2633220)
