---
title: "Non-Projective Dependency Parsing in Expected — Nivre 2009"
description: "Non-projective dependency trees, where a subtree's words are not contiguous in the sentence, are hard to parse efficiently."
authors: ["Joakim Nivre"]
year: 2009
venue: "Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP"
source: "https://aclanthology.org/P09-1040/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/nivre-2009-non-projective-dependency-parsing-expected/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/nivre-2009-non-projective-dependency-parsing-expected/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2009](https://md.research.elamur.ai/free/en/papers/2009/) / Non-Projective Dependency Parsing in Expected Linear Time

# Non-Projective Dependency Parsing in Expected Linear Time

**Authors:** [Joakim Nivre](https://md.research.elamur.ai/free/en/authors/joakim-nivre/) · **Year:** 2009 · **Venue:** Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/P09-1040/) · [PDF](https://aclanthology.org/P09-1040.pdf) · [OpenAlex](https://openalex.org/W2131395877)

**Citations:** 225 citations (openalex-snapshot · 2026-10-14) · [132](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
Non-projective dependency trees, where a subtree's words are not contiguous in the sentence, are hard to parse efficiently. Exact inference is often NP-hard, and deterministic parsers that cover all such trees usually need quadratic time. Nivre proposes a transition-based system that only links words adjacent on the stack but can still build any tree. It does this with one extra transition, SWAP, which moves a stack node back into the buffer and so reorders the input. The resulting system S_u is sound and complete for all dependency trees and behaves exactly like the standard projective system on projective input. Its worst-case complexity is O(n²). However, measurements on treebank data for Arabic, Czech, Danish, Slovene and Turkish show that the number of transitions grows linearly with sentence length, staying close to the 2n of a projective parser. A deterministic, classifier-guided parser built on S_u reaches state-of-the-art accuracy and is especially strong on labeled exact match. This offers a simple, fast and easy-to-implement way to handle discontinuous constructions.

## Key points
- The transition set extends the projective system T_p (LEFT-ARC, RIGHT-ARC, SHIFT) with SWAP to form T_u. Typically the parser runs in linear time, O(n), its best case, while the quadratic O(n²) worst case seldom arises.
- Empirically, Arabic shows the smallest variance and linear coefficients and Danish the largest; for one dataset the fit was m = 2.07n (R² = 0.96) on test data. Classifier-based parsers needed fewer transitions than oracle parsers.
- S_u was compared with a projective parser (S_p), a pseudo-projective parser (S_pp), MST-06 and MST_Malt. It was best overall for Czech and second only to the MST parsers for Slovene; both languages have 1.9% non-projective arcs.
- On exact match, S_u gave the best reported results for four of the five languages, sometimes by a wide margin (Czech, Slovene).
- Attardi (2006) is equivalent to a restricted variant allowing at most two consecutive swaps, which keeps linear time but loses completeness. Covington's algorithm is complete but quadratic even in the best case.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

Topics: [Dependency parsing](https://md.research.elamur.ai/free/en/topics/dependency-parsing/)

## Cited by

Cited by

132 papers of our library cite it (of the 140673 whose bibliographies we read); 16 of them have a page here, 116 not yet.

- [Evaluation of Dependency Parsers on Unbounded Dependencies](https://md.research.elamur.ai/free/en/papers/aclbulk-2010-nivre-evaluation-dependency-parsers-unbounded-dependencies/)
- [A Cross-Task Flexible Transition Model for Arabic Tokenization, Affix Detection, Affix Labeling, POS Tagging, and Dependency Parsing](https://md.research.elamur.ai/free/en/papers/aclbulk-2013-tratz-cross-task-flexible-transition-model/)
- [Identifying Cascading Errors using Constraints in Dependency Parsing](https://md.research.elamur.ai/free/en/papers/aclbulk-2015-ng-identifying-cascading-errors-constraints-dependency/)
- [Globally Normalized Transition-Based Neural Networks](https://md.research.elamur.ai/free/en/papers/andor-2016-globally-normalized-transition-based-neural/)
- [Improved Transition-based Parsing by Modeling Characters instead of Words with LSTMs](https://md.research.elamur.ai/free/en/papers/ballesteros-2015-improved-transition-based-parsing-modeling/)
- [Top Accuracy and Fast Dependency Parsing is not a Contradiction](https://md.research.elamur.ai/free/en/papers/bohnet-2010-top-accuracy-fast-dependency-parsing/)
- [A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing](https://md.research.elamur.ai/free/en/papers/bohnet-2012-transition-based-system-joint-part/)
- [An Empirical Comparison of Parsing Methods for Stanford Dependencies](https://md.research.elamur.ai/free/en/papers/enud-2014-kong-empirical-comparison-parsing-methods-stanford/)
- [Statistical Parsing by Machine Learning from a Classical Arabic Treebank](https://md.research.elamur.ai/free/en/papers/langstream-2015-dukes-statistical-parsing-machine-learning-classical/)
- [Transition-Based Dependency Parsing with Stack Long Short-Term Memory](https://md.research.elamur.ai/free/en/papers/missing-2015-dyer-transition-based-dependency-parsing-stack/)
- ['IMS at the CoNLL 2017 UD Shared Task: CRFs and Perceptrons Meet Neural Networks'](https://md.research.elamur.ai/free/en/papers/ud-2017-bjorkelund-ims-conll-2017-ud-shared/)
- [Stanford's Graph-based Neural Dependency Parser at the CoNLL 2017 Shared Task](https://md.research.elamur.ai/free/en/papers/ud-2017-dozat-stanford-s-graph-based-neural/)
- [Approximate Dynamic Oracle for Dependency Parsing with Reinforcement Learning](https://md.research.elamur.ai/free/en/papers/ud-2018-yu-approximate-dynamic-oracle-dependency-parsing/)
- [Integrating Graph-Based and Transition-Based Dependency Parsers in the Deep Contextualized Era](https://md.research.elamur.ai/free/en/papers/ud-2020-falenska-integrating-graph-based-transition-based/)
- [Graph-to-Graph Transformer for Transition-based Dependency Parsing](https://md.research.elamur.ai/free/en/papers/ud-2020-mohammadshahi-graph-graph-transformer-transition-based/)
- [Fast and Accurate Non-Projective Dependency Tree Linearization](https://md.research.elamur.ai/free/en/papers/yu-2020-fast-accurate-non-projective-dependency/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{nivre2009non,
  title = {{Non-Projective Dependency Parsing in Expected Linear Time}},
  author = {Nivre, Joakim},
  booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
  year = {2009},
  doi = {10.3115/1687878.1687929},
  url = {https://doi.org/10.3115/1687878.1687929}
}
```

- [← previous New Features for FrameNet - WordNet Mapping](https://md.research.elamur.ai/free/en/papers/tonelli-2009-new-features-framenet-wordnet-mapping/)
- [next → Not a Simple Yes or No: Uncertainty in Indirect Answers](https://md.research.elamur.ai/free/en/papers/marneffe-2009-not-simple-yes-or-no/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/en/papers/2009/)

## References

27 references, 12 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Giuseppe Attardi. 2006. Experiments with a multi-language non-projective dependency parser. In Proceedings of CoNLL, pages 166–170. [find](https://scholar.google.com/scholar?q=Giuseppe+Attardi%2E+2006%2E+Experiments+with+a+multi%2Dlanguage+non%2Dprojective+dependency+parser%2E+In+Proceedings+of+CoNLL%2C+pages+166%E2%80%93170%2E)
2. Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of CoNLL, pages 149–164. [find](https://scholar.google.com/scholar?q=Sabine+Buchholz+and+Erwin+Marsi%2E+2006%2E+CoNLL%2DX+shared+task+on+multilingual+dependency+parsing%2E+In+Proceedings+of+CoNLL%2C+pages+149%E2%80%93164%2E) [our card](https://md.research.elamur.ai/free/en/papers/parsers-2006-buchholz-conll-x-shared-task-multilingual/)
3. Michael A. Covington. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the 39th Annual ACM Southeast Conference, pages 95– 102. [find](https://scholar.google.com/scholar?q=Michael+A%2E+Covington%2E+2001%2E+A+fundamental+algorithm+for+dependency+parsing%2E+In+Proceedings+of+the+39th+Annual+ACM+Southeast+Conference%2C+pages+95%E2%80%93+102%2E)
4. Carlos Gómez-Rodrı́guez, David Weir, and John Carroll. 2009. Parsing mildly non-projective dependency structures. In Proceedings of EACL, pages 291–299. [find](https://scholar.google.com/scholar?q=Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez%2C+David+Weir%2C+and+John+Carroll%2E+2009%2E+Parsing+mildly+non%2Dprojective+dependency+structures%2E+In+Proceedings+of+EACL%2C+pages+291%E2%80%93299%2E)
5. Keith Hall and Vaclav Novák. 2005. Corrective modeling for non-projective dependency parsing. In Proceedings of IWPT, pages 42–52. [find](https://scholar.google.com/scholar?q=Keith+Hall+and+Vaclav+Nova%CC%81k%2E+2005%2E+Corrective+modeling+for+non%2Dprojective+dependency+parsing%2E+In+Proceedings+of+IWPT%2C+pages+42%E2%80%9352%2E)
6. Jiri Havelka. 2007. Beyond projectivity: Multilingual evaluation of constraints and measures on non-projective structures. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 608–615. [find](https://scholar.google.com/scholar?q=Jiri+Havelka%2E+2007%2E+Beyond+projectivity%3A+Multilingual+evaluation+of+constraints+and+measures+on+non%2Dprojective+structures%2E+In+Proceedings+of+the+45th+Annual+Meeting+of+the+Association+of+Computational)
7. Richard Johansson and Pierre Nugues. 2007. Incremental dependency parsing using online learning. In Proceedings of the Shared Task of EMNLP-CoNLL, pages 1134–1138. [find](https://scholar.google.com/scholar?q=Richard+Johansson+and+Pierre+Nugues%2E+2007%2E+Incremental+dependency+parsing+using+online+learning%2E+In+Proceedings+of+the+Shared+Task+of+EMNLP%2DCoNLL%2C+pages+1134%E2%80%931138%2E)
8. Marco Kuhlmann and Joakim Nivre. 2006. Mildly non-projective dependency structures. In Proceedings of the COLING/ACL Main Conference Poster Sessions, pages 507–514. [find](https://scholar.google.com/scholar?q=Marco+Kuhlmann+and+Joakim+Nivre%2E+2006%2E+Mildly+non%2Dprojective+dependency+structures%2E+In+Proceedings+of+the+COLING%2FACL+Main+Conference+Poster+Sessions%2C+pages+507%E2%80%93514%2E)
9. Marco Kuhlmann and Giorgio Satta. 2009. Treebank grammar techniques for non-projective dependency parsing. In Proceedings of EACL, pages 478–486. [find](https://scholar.google.com/scholar?q=Marco+Kuhlmann+and+Giorgio+Satta%2E+2009%2E+Treebank+grammar+techniques+for+non%2Dprojective+dependency+parsing%2E+In+Proceedings+of+EACL%2C+pages+478%E2%80%93486%2E)
10. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of EACL, pages 81–88. [find](https://scholar.google.com/scholar?q=Ryan+McDonald+and+Fernando+Pereira%2E+2006%2E+Online+learning+of+approximate+dependency+parsing+algorithms%2E+In+Proceedings+of+EACL%2C+pages+81%E2%80%9388%2E) [our card](https://md.research.elamur.ai/free/en/papers/continual-2006-mcdonald-online-learning-approximate-dependency-parsing/)
11. Ryan McDonald and Giorgio Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proceedings of IWPT, pages 122–131. [find](https://scholar.google.com/scholar?q=Ryan+McDonald+and+Giorgio+Satta%2E+2007%2E+On+the+complexity+of+non%2Dprojective+data%2Ddriven+dependency+parsing%2E+In+Proceedings+of+IWPT%2C+pages+122%E2%80%93131%2E)
12. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005a. Online large-margin training of dependency parsers. In Proceedings of ACL, pages 91– 98. [find](https://scholar.google.com/scholar?q=Ryan+McDonald%2C+Koby+Crammer%2C+and+Fernando+Pereira%2E+2005a%2E+Online+large%2Dmargin+training+of+dependency+parsers%2E+In+Proceedings+of+ACL%2C+pages+91%E2%80%93+98%2E) [our card](https://md.research.elamur.ai/free/en/papers/narrative-2005-mcdonald-online-large-margin-training-dependency/)
13. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of HLT/EMNLP, pages 523–530. [find](https://scholar.google.com/scholar?q=Ryan+McDonald%2C+Fernando+Pereira%2C+Kiril+Ribarov%2C+and+Jan+Hajic%CC%8C%2E+2005b%2E+Non%2Dprojective+dependency+parsing+using+spanning+tree+algorithms%2E+In+Proceedings+of+HLT%2FEMNLP%2C+pages+523%E2%80%93530%2E) [our card](https://md.research.elamur.ai/free/en/papers/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/)
14. Ryan McDonald, Kevin Lerman, and Fernando Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proceedings of CoNLL, pages 216–220. [find](https://scholar.google.com/scholar?q=Ryan+McDonald%2C+Kevin+Lerman%2C+and+Fernando+Pereira%2E+2006%2E+Multilingual+dependency+analysis+with+a+two%2Dstage+discriminative+parser%2E+In+Proceedings+of+CoNLL%2C+pages+216%E2%80%93220%2E) [our card](https://md.research.elamur.ai/free/en/papers/mcdonald-2006-multilingual-dependency-analysis-two-stage/)
15. Peter Neuhaus and Norbert Bröker. 1997. The complexity of recognition of linguistically adequate dependency grammars. In Proceedings of ACL/EACL, pages 337–343. [find](https://scholar.google.com/scholar?q=Peter+Neuhaus+and+Norbert+Bro%CC%88ker%2E+1997%2E+The+complexity+of+recognition+of+linguistically+adequate+dependency+grammars%2E+In+Proceedings+of+ACL%2FEACL%2C+pages+337%E2%80%93343%2E)
16. Joakim Nivre and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proceedings of ACL, pages 950–958. [find](https://scholar.google.com/scholar?q=Joakim+Nivre+and+Ryan+McDonald%2E+2008%2E+Integrating+graph%2Dbased+and+transition%2Dbased+dependency+parsers%2E+In+Proceedings+of+ACL%2C+pages+950%E2%80%93958%2E) [our card](https://md.research.elamur.ai/free/en/papers/nivre-2008-integrating-graph-based-transition-based/)
17. Joakim Nivre and Jens Nilsson. 2005. Pseudo-projective dependency parsing. In Proceedings of ACL, pages 99–106. [find](https://scholar.google.com/scholar?q=Joakim+Nivre+and+Jens+Nilsson%2E+2005%2E+Pseudo%2Dprojective+dependency+parsing%2E+In+Proceedings+of+ACL%2C+pages+99%E2%80%93106%2E) [our card](https://md.research.elamur.ai/free/en/papers/nivre-2005-pseudo-projective-dependency-parsing/)
18. Joakim Nivre, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Proceedings of CoNLL, pages 49–56. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2C+Johan+Hall%2C+and+Jens+Nilsson%2E+2004%2E+Memory%2Dbased+dependency+parsing%2E+In+Proceedings+of+CoNLL%2C+pages+49%E2%80%9356%2E) [our card](https://md.research.elamur.ai/free/en/papers/nivre-2004-memory-based-dependency-parsing/)
19. Joakim Nivre, Johan Hall, Jens Nilsson, Gülsen Eryiğit, and Svetoslav Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proceedings of CoNLL, pages 221–225. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2C+Johan+Hall%2C+Jens+Nilsson%2C+Gu%CC%88lsen+Eryig%CC%86it%2C+and+Svetoslav+Marinov%2E+2006%2E+Labeled+pseudo%2Dprojective+dependency+parsing+with+support+vector+machines%2E+In+Proceedings+of+CoNLL%2C+pages+221%E2%80%93225) [our card](https://md.research.elamur.ai/free/en/papers/nivre-2006-labeled-pseudo-projective-dependency-parsing/)
20. Joakim Nivre. 2004. Incrementality in deterministic dependency parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together (ACL), pages 50–57. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2004%2E+Incrementality+in+deterministic+dependency+parsing%2E+In+Proceedings+of+the+Workshop+on+Incremental+Parsing%3A+Bringing+Engineering+and+Cognition+Together+%28ACL%29%2C+pages+50%E2%80%9357%2E) [our card](https://md.research.elamur.ai/free/en/papers/nivre-2004-incrementality-deterministic-dependency-parsing/)
21. Joakim Nivre. 2006. Constraints on non-projective dependency graphs. In Proceedings of EACL, pages 73–80. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2006%2E+Constraints+on+non%2Dprojective+dependency+graphs%2E+In+Proceedings+of+EACL%2C+pages+73%E2%80%9380%2E)
22. Joakim Nivre. 2007. Incremental non-projective dependency parsing. In Proceedings of NAACL HLT, pages 396–403. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2007%2E+Incremental+non%2Dprojective+dependency+parsing%2E+In+Proceedings+of+NAACL+HLT%2C+pages+396%E2%80%93403%2E)
23. Joakim Nivre. 2008a. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:513–553. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2008a%2E+Algorithms+for+deterministic+incremental+dependency+parsing%2E+Computational+Linguistics%2C+34%3A513%E2%80%93553%2E) [our card](https://md.research.elamur.ai/free/en/papers/narrative-2008-nivre-algorithms-deterministic-incremental-dependency-parsing/)
24. Joakim Nivre. 2008b. Sorting out dependency parsing. In Proceedings of the 6th International Conference on Natural Language Processing (GoTAL), pages 16–27. [find](https://scholar.google.com/scholar?q=Joakim+Nivre%2E+2008b%2E+Sorting+out+dependency+parsing%2E+In+Proceedings+of+the+6th+International+Conference+on+Natural+Language+Processing+%28GoTAL%29%2C+pages+16%E2%80%9327%2E)
25. Ivan Titov and James Henderson. 2007. A latent variable model for generative dependency parsing. In Proceedings of IWPT, pages 144–155. [find](https://scholar.google.com/scholar?q=Ivan+Titov+and+James+Henderson%2E+2007%2E+A+latent+variable+model+for+generative+dependency+parsing%2E+In+Proceedings+of+IWPT%2C+pages+144%E2%80%93155%2E)
26. Ivan Titov, James Henderson, Paola Merlo, and Gabriele Musillo. 2009. Online graph planarization for synchronous parsing of semantic and syntactic dependencies. In Proceedings of IJCAI. [find](https://scholar.google.com/scholar?q=Ivan+Titov%2C+James+Henderson%2C+Paola+Merlo%2C+and+Gabriele+Musillo%2E+2009%2E+Online+graph+planarization+for+synchronous+parsing+of+semantic+and+syntactic+dependencies%2E+In+Proceedings+of+IJCAI%2E)
27. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT, pages 195–206. [find](https://scholar.google.com/scholar?q=Hiroyasu+Yamada+and+Yuji+Matsumoto%2E+2003%2E+Statistical+dependency+analysis+with+support+vector+machines%2E+In+Proceedings+of+IWPT%2C+pages+195%E2%80%93206%2E) [our card](https://md.research.elamur.ai/free/en/papers/parsers-2003-yamada-statistical-dependency-analysis-support-vector/)