Grammar Factorization with Treewidth

Abstract

We describe the application of the graph theoretic property treewidth to the problem of finding
efficient parsing algorithms. This method, similar to the junction tree algorithm (Jensen,
Lauritzen, and Olesen 1990; Shafer and Shenoy 1990) 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 (Vijay-Shankar,
Weir, and Joshi 1987). 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.