Friday, November 12, 2010
12:45 PM
CSB 703
Dan Gildea
University of Rochester
Grammar Factorization by Tree Decomposition
Abstract:
We describe the application of the graph-theoretic property known
as treewidth to the problem of finding efficient parsing
algorithms. This method, similar to the junction tree algorithm
used in graphical models for machine learning, allows automatic
discovery of efficient algorithms such as the O(n^4) algorithm
for bilexical grammars of Eisner and Satta (1999). We examine
the complexity of applying this method to parsing algorithms for
general Linear Context-Free Rewriting Systems (LCFRS). We show
that any polynomial-time algorithm for this problem would imply
an improved approximation algorithm for the well-studied
treewidth problem on general graphs.