2020/03/30 by Caio Corro, Corro, Caio
Computer Science · #Algorithms and Data Compression #Computation and Language (cs.CL) #FOS: Computer and information sciences #Natural Language Processing Techniques #Topic Modeling
paper · pdf · doi:10.48550/arxiv.2003.13785
openalex publication_date 2020/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n6)\ndown to mathcal O(n3). 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