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

We introduce a novel chart-based algorithm for span-based parsing of\ndiscontinuous constituency trees of block degree two, including ill-nested\nstructures. In particular, we show that we can build variants of our parser\nwith smaller search spaces and time complexities ranging from $\\mathcal O(n^6)$\ndown to $\\mathcal O(n^3)$. The cubic time variant covers 98\\% of constituents\nobserved in linguistic treebanks while having the same complexity as continuous\nconstituency parsers. We evaluate our approach on German and English treebanks\n(Negra, Tiger and Discontinuous PTB) and report state-of-the-art results in the\nfully supervised setting. We also experiment with pre-trained word embeddings\nand \\bert{}-based neural networks.\n