Skip to main content Skip to main navigation


Weighted deductive parsing and Knuth's algorithm

Mark-Jan Nederhof
In: Computational Linguistics (CL), Vol. 29, No. 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.

Weitere Links