@InProceedings{shi-gmezrodrguez-lee:2018:N18-2,
  author    = {Shi, Tianze  and  Gómez-Rodríguez, Carlos  and  Lee, Lillian},
  title     = {Improving Coverage and Runtime Complexity for Exact Inference in Non-Projective Transition-Based Dependency Parsers},
  booktitle = {Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)},
  month     = {June},
  year      = {2018},
  address   = {New Orleans, Louisiana},
  publisher = {Association for Computational Linguistics},
  pages     = {420--425},
  abstract  = {We generalize Cohen, Gómez-Rodrí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.},
  url       = {http://www.aclweb.org/anthology/N18-2067}
}