# Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Mar 2020.

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

- [Headed-Span-Based Projective Dependency Parsing](https://mlsanity.com/paper/2108.04750/) (2021)
- [Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars](https://mlsanity.com/paper/2212.09140/) (2022)
- [Reducing Discontinuous to Continuous Parsing with Pointer Network Reordering](https://mlsanity.com/paper/2104.06239/) (2021)
- [Discontinuous Grammar as a Foreign Language](https://mlsanity.com/paper/2110.10431/) (2021)
- [A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2)](https://mlsanity.com/paper/2210.04738/) (2022)
- [Approximating CKY with Transformers](https://mlsanity.com/paper/2305.02386/) (2023)
- [On the inconsistency of separable losses for structured prediction](https://mlsanity.com/paper/2301.10810/) (2023)
- [On graph-based reentrancy-free semantic parsing](https://mlsanity.com/paper/2302.07679/) (2023)
- [Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing](https://mlsanity.com/paper/2403.00143/) (2024)
- [Formal Constraints on Dependency Syntax](https://mlsanity.com/paper/2604.04542/) (2026)
- [Exploiting Pre-trained Encoder-Decoder Transformers for Sequence-to-Sequence Constituent Parsing](https://mlsanity.com/paper/2605.13373/) (2026)

## Abstract (arXiv)

We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from mathcal O(n6) down to mathcal O(n3). The cubic time variant covers 98% of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on German and English treebanks (Negra, Tiger and Discontinuous PTB) and report state-of-the-art results in the fully supervised setting. We also experiment with pre-trained word embeddings and bert-based neural networks.