# Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers

arXiv: https://arxiv.org/abs/1804.10615 · HTML: https://mlsanity.com/paper/1804.10615/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2018.

## Built on by (most cited first, 1 of 1)

- [Formal Constraints on Dependency Syntax](https://mlsanity.com/paper/2604.04542/) (2026)

## Abstract (arXiv)

We generalize Cohen, G'omez-Rodr'iguez, and Satta's (2011) parser to a family of non-projective transition-based dependency parsers allowing polynomial-time exact inference. This includes novel parsers with better coverage than Cohen et al. (2011), and even a variant that reduces time complexity to O(n6), improving over the known bounds in exact inference for non-projective transition-based parsing. We hope that this piece of theoretical work inspires design of novel transition systems with better coverage and better run-time guarantees. Code available at https://github.com/tzshi/nonproj-dp-variants-naacl2018