Research and Advances

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.


Author Archives

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved