DFKI-LT - Weighted deductive parsing and Knuth's algorithm

Mark-Jan Nederhof
Weighted deductive parsing and Knuth's algorithm
1 Computational Linguistics volume 29 number 1, Pages 135-143, 2003
 
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.
 
Files: BibTeX, Nederhof:2003:WDP.pdf