Paper Info
Title
How to Multiply Dynamic Programming Algorithms
Abstract
We develop a theory of algebraic operations over linear grammars that makes it possible to combine simple \"atomic\" grammars operating on single sequences into complex, multi-dimensional grammars. We demonstrate the utility of this framework by constructing the search spaces of complex alignment problems on multiple input sequences explicitly as algebraic expressions of very simple 1-dimensional grammars. The compiler accompanying our theory makes it easy to experiment with the combination of multiple grammars and different operations. Composite grammars can be written out in <InlineEquation ID=\"IEq1\" <EquationSource Format=\"TEX\"${\\hbox{\\LaTeX}}$</EquationSource> </InlineEquation> for documentation and as a guide to implementation of dynamic programming algorithms. An embedding in Haskell as a domain-specific language makes the theory directly accessible to writing and using grammar products without the detour of an external compiler. <ExternalRef> <RefSource> <Emphasis FontCategory=\"NonProportional\"http://www.bioinf.uni-leipzig.de/Software/gramprod/</Emphasis> </RefSource> <RefTarget Address=\"http://www.bioinf.uni-leipzig.de/Software/gramprod/\" TargetType=\"URL\"/ </ExternalRef>
Year
DOI
Venue
2013
10.1007/978-3-319-02624-4_8
BSB
Keywords
Field
DocType
linear grammar,context free grammar,product structure,multiple alignment,Haskell
Context-sensitive grammar,Context-free grammar,Programming language,Computer science,Indexed grammar,Theoretical computer science,Artificial intelligence,Stochastic context-free grammar,Tree-adjoining grammar,Embedded pushdown automaton,L-attributed grammar,Algorithm,Parsing expression grammar,Machine learning
Conference
Volume
ISSN
Citations 
8213
0302-9743
5
PageRank 
References 
Authors
0.46
12
3
Name
Order
Citations
PageRank
Christian Höner Zu Siederdissen117113.01
Ivo L. Hofacker21669131.57
Peter F. Stadler31839152.96