%0 Conference Paper %1 mcDonald2007 %A McDonald, Ryan %A Satta, Giorgio %B Proceedings of the 10th International Conference on Parsing Technologies %C Stroudsburg, PA, USA %D 2007 %I Association for Computational Linguistics %K dependency english example grammar non non-projective projective projectivity scheduled sentence %P 121--132 %T On the complexity of non-projective data-driven dependency parsing %U http://dl.acm.org/citation.cfm?id=1621410.1621426 %X 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. %@ 978-1-932432-90-9

@inproceedings{mcDonald2007, 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.}, acmid = {1621426}, added-at = {2012-10-22T00:09:56.000+0200}, address = {Stroudsburg, PA, USA}, author = {McDonald, Ryan and Satta, Giorgio}, biburl = {https://www.bibsonomy.org/bibtex/2171233763fbbe510d06ff306fbdb52fd/jil}, booktitle = {Proceedings of the 10th International Conference on Parsing Technologies}, description = {On the complexity of non-projective data-driven dependency parsing}, interhash = {f04f4385140e31a74060f8873c427b1d}, intrahash = {171233763fbbe510d06ff306fbdb52fd}, isbn = {978-1-932432-90-9}, keywords = {dependency english example grammar non non-projective projective projectivity scheduled sentence}, location = {Prague, Czech REpublic}, numpages = {12}, pages = {121--132}, publisher = {Association for Computational Linguistics}, series = {IWPT '07}, timestamp = {2013-11-23T20:11:51.000+0100}, title = {On the complexity of non-projective data-driven dependency parsing}, url = {http://dl.acm.org/citation.cfm?id=1621410.1621426}, year = 2007 }