Squibs and Discussions: Weighted Deductive Parsing and Knuth’s Algorithm
By Mark-Jan Nederhof. 2003
84 citations recorded by the source corpus.
We discuss weighted deductive parsing and consider the problem of finding the derivation with the lowest weight. We show that Knuth's generalization of Dijkstra's algorithm for the shortest-path problem offers a general method to solve this problem. Our approach is modular in the sense that Knuth's algorithm is formulated independently from the weighted deduction system.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Molecular Biology, Natural Language Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Chris Dyer
- Yoav Goldberg
- Phil Blunsom
- Graham Neubig
- Liang Huang
- Noah A. Smith
- Yonatan Belinkov
- Felix Stahlberg
In Computational Theory and Mathematics
- Wei Dang Lu
- Liang Huang
- Adam Lopez
- David Chiang
- Phil Blunsom
- Chris Dyer
- Juri Ganitkevitch
- Zhanming Jie
In Molecular Biology
- Wei Dang Lu
- Liang Huang
- David Chiang
- Phil Blunsom
- Chris Dyer
- Juri Ganitkevitch
- Zhanming Jie
- Jierui Li
In Natural Language Processing
- Chris Dyer
- Phil Blunsom
- Philipp Koehn
- Noah A. Smith
- Mirella Lapata
- Graham Neubig
- Yoav Goldberg
- Christopher D. Manning
Citations in the corpus
- Learning to Reason Deductively: Math Word Problem Solving as Complex Relation Extraction (2022, methodology): “Following the standard deduction systems (Shieber et al., 1995; Nederhof, 2003), the reasoning process can be formulated in Figure 2.”
- Better k-best Parsing (2005, methodology): “We can therefore take laziness to an extreme by delaying the whole k -best calculation until after parsing.”
- cdec: A Decoder, Alignment, and Learning Framework for Finite- State and Context-Free Translation Models (2010, background): “In this view, translation (or tagging) deductions have the structure of a context-free forest, or directed hypergraph, where edges have a single head and 0 or more tail nodes (Nederhof, 2003).”