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