@inproceedings{shi-etal-2018-improving,
    title = "Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers",
    author = "Shi, Tianze  and
      G{\'o}mez-Rodr{\'i}guez, Carlos  and
      Lee, Lillian",
    editor = "Walker, Marilyn  and
      Ji, Heng  and
      Stent, Amanda",
    booktitle = "Proceedings of the 2018 Conference of the North {A}merican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)",
    month = jun,
    year = "2018",
    address = "New Orleans, Louisiana",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/Add-Cong-Liu-Florida-Atlantic-University-author-id/N18-2067/",
    doi = "10.18653/v1/N18-2067",
    pages = "420--425",
    abstract = "We generalize Cohen, G{\'o}mez-Rodr{\'i}guez, and Satta`s (2011) parser to a family of non-projective transition-based dependency parsers allowing polynomial-time exact inference. This includes novel parsers with better coverage than Cohen et al. (2011), and even a variant that reduces time complexity to $O(n^6)$, improving over the known bounds in exact inference for non-projective transition-based parsing. We hope that this piece of theoretical work inspires design of novel transition systems with better coverage and better run-time guarantees."
}