Paper: Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems

ACL ID P11-1046
Title Optimal Head-Driven Parsing Complexity for Linear Context-Free Rewriting Systems
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2011
Authors

We study the problem of finding the best head- driven parsing strategy for Linear Context- Free Rewriting System productions. A head- driven strategy must begin with a specified righthand-side nonterminal (the head) and add the remaining nonterminals one at a time in any order. We show that it is NP-hard to find the best head-driven strategy in terms of either the time or space complexity of parsing.