@inproceedings{coavoux-cohen-2019-discontinuous,
    title = "Discontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle",
    author = "Coavoux, Maximin  and
      Cohen, Shay B.",
    editor = "Burstein, Jill  and
      Doran, Christy  and
      Solorio, Thamar",
    booktitle = "Proceedings of the 2019 Conference of the North {A}merican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)",
    month = jun,
    year = "2019",
    address = "Minneapolis, Minnesota",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/fix-sig-urls/N19-1018/",
    doi = "10.18653/v1/N19-1018",
    pages = "204--217",
    abstract = "We introduce a novel transition system for discontinuous constituency parsing. Instead of storing subtrees in a stack {--}i.e. a data structure with linear-time sequential access{--} the proposed system uses a set of parsing items, with constant-time random access. This change makes it possible to construct any discontinuous constituency tree in exactly $4n–2$ transitions for a sentence of length n. At each parsing step, the parser considers every item in the set to be combined with a focus item and to construct a new constituent in a bottom-up fashion. The parsing strategy is based on the assumption that most syntactic structures can be parsed incrementally and that the set {--}the memory of the parser{--} remains reasonably small on average. Moreover, we introduce a provably correct dynamic oracle for the new transition system, and present the first experiments in discontinuous constituency parsing using a dynamic oracle. Our parser obtains state-of-the-art results on three English and German discontinuous treebanks."
}