Algebraic dynamic programming on trees

DOI10.3390/A10040135MaRDI QIDQ2633220zbMATH OpenOpenAlexWikidataFDO

Authors Sarah J. Berkemer, Christian Höner zu Siederdissen, Peter F. Stadler

Publication date 8 May 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a10040135

zbMATH Keywords

dynamic programmingformal languagetree alignmenttree editing

Mathematics Subject Classification ID

Dynamic programming (90C39) Grammars and rewriting systems (68Q42) Functional programming and lambda calculus (68N18)

Recommendations

• Algebraic dynamic programming for multiple context-free grammars
• Algebraic dynamic programming
• scientific article; zbMATH DE number 2090016
• A discipline of dynamic programming over sequence data
• Counting, Generating and Sampling Tree Alignments

Cites work

• scientific article; zbMATH DE number 3361265 (Why is no real title available?)
• 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
• 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
• RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
• Regular, shape-polymorphic, parallel arrays in Haskell
• 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

Cited in

(5)

• scientific article; zbMATH DE number 2090016 (Why is no real title available?)
• Algebraic dynamic programming
• Algebraic dynamic programming for multiple context-free grammars
• Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
• Compositional properties of alignments

Describes a project that uses

Uses Software

• TED
• ecceTERA
• RNAforester
• ViennaRNA
• Haskell

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)