@inproceedings{corro-2020-span,
    title = "Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from {O}(n{\textasciicircum}6) down to {O}(n{\textasciicircum}3)",
    author = "Corro, Caio",
    editor = "Webber, Bonnie  and
      Cohn, Trevor  and
      He, Yulan  and
      Liu, Yang",
    booktitle = "Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)",
    month = nov,
    year = "2020",
    address = "Online",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/jlcl-multiple-ingestion/2020.emnlp-main.219/",
    doi = "10.18653/v1/2020.emnlp-main.219",
    pages = "2753--2764",
    abstract = "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 O(n{\textasciicircum}6) down to O(n{\textasciicircum}3). 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 DPTB) 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."
}