@jil

On the complexity of non-projective data-driven dependency parsing

, and . Proceedings of the 10th International Conference on Parsing Technologies, page 121--132. Stroudsburg, PA, USA, Association for Computational Linguistics, (2007)

Abstract

In this paper we investigate several non-projective parsing algorithms for dependency 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 nonlocal information, and present several hardness results. This suggests that it is unlikely that exact non-projective dependency parsing is tractable for any model richer than the edge-factored model.

Description

On the complexity of non-projective data-driven dependency parsing

Links and resources

URL:
BibTeX key:
mcDonald2007
search on:

Comments and Reviews  
(0)

There is no review or comment yet. You can write one!

Tags


Cite this publication