Paper: Computational Complexity Of Probabilistic Disambiguation By Means Of Tree-Grammars

ACL ID C96-2215
Title Computational Complexity Of Probabilistic Disambiguation By Means Of Tree-Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1996
Authors

This paper studies the computational complexity of disambiguation under probabilistic tree-grammars as in (Bod, 1992; Schabes and Waters, 1993). It presents a proof that the following prob- lems are NP-hard: computing the Most Probable Parse from a sentence or from a word-graph, and computing the Most Probable Sentence (MPS) from a word- graph. The NP-hardness of comput- ing the MPS from a word-graph also holds for Stochastic Context-Free Gram- mars (SCFGs). 1 Motivation Statistical disambiguation is currently a pop- ular technique in parsing Natural Language. Among the models that implement statistical disambiguation one finds the models that em- ploy Tree-Grammars such as Data Oriented Parsing (DOP) (Scha, 1990; nod, 1992) and Stochastic (Lexicalized) Tree-Adjoining Grammar (STAG) (Schab...