Weighted Derivation Trees

The nodes of a weighted derivation tree are associated
with weighting functions over the vocabulary 
of a context-free grammar.  An algorithm is presented
for constructing the optimal derivation tree having 
the same structure as a given weighted derivation tree.
 In addition, the correctness of the algorithm 
is established.  The method may be applied to problems
involving probabilistic parsing or combinatorial 
optimization.

CACM September, 1976

Loui, M. C.

derivation tree, parse tree, probabilistic grammar,
structural ambiguity, combinatorial optimization

5.23 5.49

CA760903 JB January 4, 1978  9:41 AM

2836	5	2836
2836	5	2836
2836	5	2836