---
title: "Finding Optimal 1-Endpoint-Crossing Trees — Pitler 2013"
description: "The authors propose a new structural class, 1-Endpoint-Crossing trees: whenever an arc is crossed… 22 references, cited by 26 papers here."
authors: ["Emily Pitler", "Sampath Kannan", "Mitchell Marcus"]
year: 2013
venue: "Transactions of the Association for Computational Linguistics"
source: "https://aclanthology.org/Q13-1002/"
doi: "10.1162/tacl_a_00206"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/pitler-2013-finding-optimal-1-endpoint-crossing/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/pitler-2013-finding-optimal-1-endpoint-crossing/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2013](https://md.research.elamur.ai/free/en/papers/2013/page/2/) / Finding Optimal 1-Endpoint-Crossing Trees

# Finding Optimal 1-Endpoint-Crossing Trees

**Authors:** [Emily Pitler](https://md.research.elamur.ai/free/en/authors/emily-pitler/), Sampath Kannan and [Mitchell Marcus](https://md.research.elamur.ai/free/en/authors/mitchell-marcus/) · **Year:** 2013 · **Venue:** [Transactions of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/tacl/) ([Transactions of the Association for Computational Linguistics (TACL) 2013](https://md.research.elamur.ai/free/en/venues/tacl/2013/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/Q13-1002/) · [PDF](https://aclanthology.org/Q13-1002.pdf) · [DOI 10.1162/tacl\_a\_00206](https://doi.org/10.1162/tacl_a_00206) · [OpenAlex](https://openalex.org/W2142521780)

**Citations:** 43 citations (OpenAlex, 2026-10-14) · 26 in our library, of the 149,439 papers whose bibliographies we read

## Summary
Dependency parsers that allow crossing arcs have usually been much slower than projective ones. The projective O(n³) algorithm misses many real sentences. Unrestricted spanning trees become NP-hard to decode once grandparent or sibling features are added. Existing mildly non-projective classes need costly algorithms, such as O(n⁷) for well-nested trees with block degree 2. The authors propose a new structural class, 1-Endpoint-Crossing trees: whenever an arc is crossed, every arc crossing it meets at a single shared vertex.

Using the CoNLL-X training treebanks for six languages, they show this class captures nearly all annotated parses. They prove that each arc, together with its shared crossing vertex, splits the tree into self-contained regions, each an interval plus one outside vertex. Based on this, they design an exact arc-factored dynamic program that finds the best such tree in O(n⁴). That is faster than any earlier mildly non-projective decoder.

The class also links to theory. It is strictly contained in 2-planar graphs, and pairs of cross-serial verbs yield trees of this type.

## Key points
- Coverage on the CoNLL-X training data (Arabic, Czech, Danish, Dutch, Portuguese, Swedish) is 95.8–99.8%. Dutch is the lowest and reaches 97.0% if arcs from the artificial root are ignored.
- The class is compared with three others:
  - projective trees: O(n³), coverage as low as 63.6% for Dutch;
  - gap-minding trees: O(n⁵), 90.4–97.7%;
  - well-nested trees with block degree 2: O(n⁷), 95.4–99.9%.
- The O(n⁴) algorithm combines five kinds of subproblems: plain intervals, plus four variants of interval-with-exterior-point regions. The variants differ in whether arcs from the outside vertex can be crossed by arcs at the left boundary, the right boundary, both, or neither.
- 1-Endpoint-Crossing trees form a proper subset of 2-planar trees, a class previously handled only by a transition-based parser with no known exact algorithm. They are not a subset of the well-nested, block-degree-2 class.

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

## Institutions

- [University of Pennsylvania](https://md.research.elamur.ai/free/en/universities/university-of-pennsylvania/) — University, Philadelphia, United States · 221 works · 63,234 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 252 works

## Cite

Cite as: Emily Pitler, Sampath Kannan and Mitchell Marcus. 2013. Finding Optimal 1-Endpoint-Crossing Trees. Transactions of the Association for Computational Linguistics.

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

```bibtex
@article{pitler2013finding,
  title = {{Finding Optimal 1-Endpoint-Crossing Trees}},
  author = {Emily Pitler, Sampath Kannan and Mitchell Marcus},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2013},
  doi = {10.1162/tacl\_a\_00206},
  url = {https://doi.org/10.1162/tacl_a_00206}
}
```

- [← previous Annotating the meaning of discourse connectives by looking at their translation: The translation-spotting technique](https://md.research.elamur.ai/free/en/papers/cartoni-2013-annotating-meaning-discourse-connectives-looking/)
- [next → Classifying English Documents by National Dialect](https://md.research.elamur.ai/free/en/papers/lui-2013-classifying-english-documents-national-dialect/)
- [↑ back to papers of 2013](https://md.research.elamur.ai/free/en/papers/2013/page/2/)

## References

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

1. E. Bach, C. Brown, and W. Marslen-Wilson. 1986. Crossed and nested dependencies in german and dutch: A psycholinguistic study. Language and Cognitive Processes, 1(4):249–262. [find](https://scholar.google.com/scholar?q=E%2E+Bach%2C+C%2E+Brown%2C+and+W%2E+Marslen%2DWilson%2E+1986%2E+Crossed+and+nested+dependencies+in+german+and+dutch%3A+A+psycholinguistic+study%2E+Language+and+Cognitive+Processes%2C+1%284%29%3A249%E2%80%93262%2E)
2. F. Bernhart and P.C. Kainen. 1979. The book thickness of a graph. Journal of Combinatorial Theory, Series B, 27(3):320 – 331. [find](https://scholar.google.com/scholar?q=F%2E+Bernhart+and+P%2EC%2E+Kainen%2E+1979%2E+The+book+thickness+of+a+graph%2E+Journal+of+Combinatorial+Theory%2C+Series+B%2C+27%283%29%3A320+%E2%80%93+331%2E)
3. M. Bodirsky, M. Kuhlmann, and M. Möhl. 2005. Well-nested drawings as models of syntactic structure. In In Tenth Conference on Formal Grammar and Ninth Meeting on Mathematics of Language, pages 88–1. [find](https://scholar.google.com/scholar?q=M%2E+Bodirsky%2C+M%2E+Kuhlmann%2C+and+M%2E+M%C3%B6hl%2E+2005%2E+Well%2Dnested+drawings+as+models+of+syntactic+structure%2E+In+In+Tenth+Conference+on+Formal+Grammar+and+Ninth+Meeting+on+Mathematics+of+Language%2C+pages+88%E2%80%931%2E)
4. University Press. X. Carreras. 2007. [Experiments with a higher-order projective dependency parser](https://md.research.elamur.ai/free/en/papers/carreras-2007-experiments-higher-order-projective-dependency/). In Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL, volume 7, pages 957–961. N. Chomsky, Massachusetts Institute of Technology. Dept. of Linguistics, and Philosophy. 1998. Minimalist inquir…
5. N. Chomsky. 1981. Lectures on Government and Binding. [find](https://scholar.google.com/scholar?q=N%2E+Chomsky%2E+1981%2E+Lectures+on+Government+and+Binding%2E)
6. Dordrecht: Foris. F. Chung, F. Leighton, and A. Rosenberg. 1987. Embedding graphs in books: A layout problem with applications to VLSI design. SIAM Journal on Algebraic Discrete Methods, 8(1):33–58. [find](https://scholar.google.com/scholar?q=Dordrecht%3A+Foris%2E+F%2E+Chung%2C+F%2E+Leighton%2C+and+A%2E+Rosenberg%2E+1987%2E+Embedding+graphs+in+books%3A+A+layout+problem+with+applications+to+VLSI+design%2E+SIAM+Journal+on+Algebraic+Discrete+Methods%2C+8%281%29%3A33%E2%80%9358%2E)
7. H. Cui, R. Sun, K. Li, M.Y. Kan, and T.S. Chua. 2005. Question answering passage retrieval using dependency relations. In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, pages 400–407. [find](https://scholar.google.com/scholar?q=H%2E+Cui%2C+R%2E+Sun%2C+K%2E+Li%2C+M%2EY%2E+Kan%2C+and+T%2ES%2E+Chua%2E+2005%2E+Question+answering+passage+retrieval+using+dependency+relations%2E+In+Proceedings+of+the+28th+annual+international+ACM+SIGIR+conference+on+Research+)
8. ACM. A. Culotta and J. Sorensen. 2004. [Dependency tree kernels for relation extraction](https://md.research.elamur.ai/free/en/papers/culotta-2004-dependency-tree-kernels-relation-extraction/). In Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, page 423. Association for Computational Linguistics.
9. Y. Ding and M. Palmer. 2005. [Machine translation using probabilistic synchronous dependency insertion grammars](https://md.research.elamur.ai/free/en/papers/ding-2005-machine-translation-probabilistic-synchronous-dependency/). In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, pages 541–548. Association for Computational Linguistics.
10. J. Eisner. 2000. Bilexical grammars and their cubic-time parsing algorithms. In Harry Bunt and Anton Nijholt, editors, Advances in Probabilistic and Other Parsing Technologies, pages 29–62. [find](https://scholar.google.com/scholar?q=J%2E+Eisner%2E+2000%2E+Bilexical+grammars+and+their+cubic%2Dtime+parsing+algorithms%2E+In+Harry+Bunt+and+Anton+Nijholt%2C+editors%2C+Advances+in+Probabilistic+and+Other+Parsing+Technologies%2C+pages+29%E2%80%9362%2E)
11. Kluwer Academic Publishers, October. S. Even and A. Itai. 1971. Queues, stacks, and graphs. In Proc. International Symp. on Theory of Machines and Computations, pages 71–86. [find](https://scholar.google.com/scholar?q=Kluwer+Academic+Publishers%2C+October%2E+S%2E+Even+and+A%2E+Itai%2E+1971%2E+Queues%2C+stacks%2C+and+graphs%2E+In+Proc%2E+International+Symp%2E+on+Theory+of+Machines+and+Computations%2C+pages+71%E2%80%9386%2E)
12. C. Gómez-Rodríguez and J. Nivre. 2010. A transition-based parser for 2-planar dependency structures. In Proceedings of ACL, pages 1492–1501. [find](https://scholar.google.com/scholar?q=C%2E+G%C3%B3mez%2DRodr%C3%ADguez+and+J%2E+Nivre%2E+2010%2E+A+transition%2Dbased+parser+for+2%2Dplanar+dependency+structures%2E+In+Proceedings+of+ACL%2C+pages+1492%E2%80%931501%2E)
13. C. Gómez-Rodríguez, J. Carroll, and D. Weir. 2011. Dependency parsing schemata and mildly non-projective dependency parsing. Computational Linguistics, 37(3):541–586. [find](https://scholar.google.com/scholar?q=C%2E+G%C3%B3mez%2DRodr%C3%ADguez%2C+J%2E+Carroll%2C+and+D%2E+Weir%2E+2011%2E+Dependency+parsing+schemata+and+mildly+non%2Dprojective+dependency+parsing%2E+Computational+Linguistics%2C+37%283%29%3A541%E2%80%93586%2E)
14. T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proceedings of ACL, pages 1–11. [find](https://scholar.google.com/scholar?q=T%2E+Koo+and+M%2E+Collins%2E+2010%2E+Efficient+third%2Dorder+dependency+parsers%2E+In+Proceedings+of+ACL%2C+pages+1%E2%80%9311%2E)
15. M. Kuhlmann. 2013. Mildly non-projective dependency grammar. Computational Linguistics, 39(2). [find](https://scholar.google.com/scholar?q=M%2E+Kuhlmann%2E+2013%2E+Mildly+non%2Dprojective+dependency+grammar%2E+Computational+Linguistics%2C+39%282%29%2E)
16. R. McDonald and F. Pereira. 2006. [Online learning of approximate dependency parsing algorithms](https://md.research.elamur.ai/free/en/papers/mcdonald-2006-online-learning-approximate-dependency-parsing/). In Proceedings of EACL, pages 81–88.
17. R. McDonald and G. Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proceedings of the 10th International Conference on Parsing Technologies, pages 121–132. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005. Non-projective dependency parsing using spanning t… [find](https://scholar.google.com/scholar?q=R%2E+McDonald+and+G%2E+Satta%2E+2007%2E+On+the+complexity+of+non%2Dprojective+data%2Ddriven+dependency+parsing%2E+In+Proceedings+of+the+10th+International+Conference+on+Parsing+Technologies%2C+pages+121%E2%80%93132%2E+R%2E+McDon)
18. E. Pitler, S. Kannan, and M. Marcus. 2012. Dynamic programming for higher order parsing of gap-minding trees. In Proceedings of EMNLP, pages 478–488. [find](https://scholar.google.com/scholar?q=E%2E+Pitler%2C+S%2E+Kannan%2C+and+M%2E+Marcus%2E+2012%2E+Dynamic+programming+for+higher+order+parsing+of+gap%2Dminding+trees%2E+In+Proceedings+of+EMNLP%2C+pages+478%E2%80%93488%2E)
19. L.A. Ringenberg. 1967. College geometry. [find](https://scholar.google.com/scholar?q=L%2EA%2E+Ringenberg%2E+1967%2E+College+geometry%2E)
20. Wiley. A. Rush and S. Petrov. 2012. Vine pruning for efficient multi-pass dependency parsing. In Proceedings of NAACL, pages 498–507. [find](https://scholar.google.com/scholar?q=Wiley%2E+A%2E+Rush+and+S%2E+Petrov%2E+2012%2E+Vine+pruning+for+efficient+multi%2Dpass+dependency+parsing%2E+In+Proceedings+of+NAACL%2C+pages+498%E2%80%93507%2E)
21. S.M. Shieber. 1985. Evidence against the context-freeness of natural language. Linguistics and Philosophy, 8(3):333–343. [find](https://scholar.google.com/scholar?q=S%2EM%2E+Shieber%2E+1985%2E+Evidence+against+the+context%2Dfreeness+of+natural+language%2E+Linguistics+and+Philosophy%2C+8%283%29%3A333%E2%80%93343%2E)
22. H. Zhang and R. McDonald. 2012. Generalized higher-order dependency parsing with cube pruning. In Proceedings of EMNLP, pages 320–331. [find](https://scholar.google.com/scholar?q=H%2E+Zhang+and+R%2E+McDonald%2E+2012%2E+Generalized+higher%2Dorder+dependency+parsing+with+cube+pruning%2E+In+Proceedings+of+EMNLP%2C+pages+320%E2%80%93331%2E)

*Updated 30 October 2026*