Paper: Optimal Parsing Strategies for Linear Context-Free Rewriting Systems

ACL ID N10-1118
Title Optimal Parsing Strategies for Linear Context-Free Rewriting Systems
Venue Human Language Technologies
Session Main Conference
Year 2010
Authors

Factorization is the operation of transforming a production in a Linear Context-Free Rewrit- ing System (LCFRS) into two simpler produc- tions by factoring out a subset of the nontermi- nals on the production’s righthand side. Fac- torization lowers the rank of a production but may increase its fan-out. We show how to apply factorization in order to minimize the parsing complexity of the resulting grammar, and study the relationship between rank, fan- out, and parsing complexity. We show that it is always possible to obtain optimum parsing complexity with rank two. However, among transformed grammars of rank two, minimum parsing complexity is not always possible with minimum fan-out. Applying our factorization algorithm to LCFRS rules extracted from de- pendency treebanks allows us to fi...