DFKI-LT - Weighted deductive parsing and Knuth's algorithm
Weighted deductive parsing and Knuth's algorithm
1 Computational Linguistics volume 29 number 1,
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