Paper: Dynamic Programming Algorithms for Transition-Based Dependency Parsers

ACL ID P11-1068
Title Dynamic Programming Algorithms for Transition-Based Dependency Parsers
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2011
Authors

We develop a general dynamic programming technique for the tabulation of transition-based dependency parsers, and apply it to obtain novel, polynomial-time algorithms for parsing with the arc-standard and arc-eager models. We also show how to reverse our technique to ob- tain new transition-based dependency parsers from existing tabular methods. Additionally, we provide a detailed discussion of the con- ditions under which the feature models com- monly used in transition-based parsing can be integrated into our algorithms.