Paper: On the Complexity of Non-Projective Data-Driven Dependency Parsing

ACL ID W07-2216
Title On the Complexity of Non-Projective Data-Driven Dependency Parsing
Venue Conference on Parsing Technologies
Session Main Conference
Year 2007
Authors

In this paper we investigate several non- projective parsing algorithms for depen- dency parsing, providing novel polynomial time solutions under the assumption that each dependency decision is independent of all the others, called here the edge-factored model. We also investigate algorithms for non-projective parsing that account for non- local information, and present several hard- ness results. This suggests that it is unlikely that exact non-projective dependency pars- ing is tractable for any model richer than the edge-factored model.