@inproceedings{stanojevic-steedman-2020-span,
    title = "Span-Based {LCFRS}-2 Parsing",
    author = "Stanojevi{\'c}, Milo{\v{s}}  and
      Steedman, Mark",
    editor = "Bouma, Gosse  and
      Matsumoto, Yuji  and
      Oepen, Stephan  and
      Sagae, Kenji  and
      Seddah, Djam{\'e}  and
      Sun, Weiwei  and
      S{\o}gaard, Anders  and
      Tsarfaty, Reut  and
      Zeman, Dan",
    booktitle = "Proceedings of the 16th International Conference on Parsing Technologies and the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies",
    month = jul,
    year = "2020",
    address = "Online",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/fix-sig-urls/2020.iwpt-1.12/",
    doi = "10.18653/v1/2020.iwpt-1.12",
    pages = "111--121",
    abstract = "The earliest models for discontinuous constituency parsers used mildly context-sensitive grammars, but the fashion has changed in recent years to grammar-less transition-based parsers that use strong neural probabilistic models to greedily predict transitions. We argue that grammar-based approaches still have something to contribute on top of what is offered by transition-based parsers. Concretely, by using a grammar formalism to restrict the space of possible trees we can use dynamic programming parsing algorithms for exact search for the most probable tree. Previous chart-based parsers for discontinuous formalisms used probabilistically weak generative models. We instead use a span-based discriminative neural model that preserves the dynamic programming properties of the chart parsers. Our parser does not use an explicit grammar, but it does use explicit grammar formalism constraints: we generate only trees that are within the LCFRS-2 formalism. These properties allow us to construct a new parsing algorithm that runs in lower worst-case time complexity of O(l n{\textasciicircum}4 +n{\textasciicircum}6), where $n$ is the sentence length and $l$ is the number of unique non-terminal labels. This parser is efficient in practice, provides best results among chart-based parsers, and is competitive with the best transition based parsers. We also show that the main bottleneck for further improvement in performance is in the restriction of fan-out to degree 2. We show that well-nestedness is helpful in speeding up parsing, but lowers accuracy."
}