{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T22:42:12Z","timestamp":1698446532118},"reference-count":36,"publisher":"MIT Press - Journals","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p> Motivated by the task of semantic parsing, we describe a transition system that generalizes standard transition-based dependency parsing techniques to generate a graph rather than a tree. Our system includes a cache with fixed size m, and we characterize the relationship between the parameter m and the class of graphs that can be produced through the graph-theoretic concept of tree decomposition. We find empirically that small cache sizes cover a high percentage of sentences in existing semantic corpora. <\/jats:p>","DOI":"10.1162\/coli_a_00308","type":"journal-article","created":{"date-parts":[[2017,12,14]],"date-time":"2017-12-14T20:23:10Z","timestamp":1513282990000},"page":"85-118","source":"Crossref","is-referenced-by-count":3,"title":["Cache Transition Systems for Graph Parsing"],"prefix":"10.1162","volume":"44","author":[{"given":"Daniel","family":"Gildea","sequence":"first","affiliation":[{"name":"University of Rochester"}]},{"given":"Giorgio","family":"Satta","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Padova"}]},{"given":"Xiaochang","family":"Peng","sequence":"additional","affiliation":[{"name":"University of Rochester"}]}],"member":"281","reference":[{"key":"bib1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"bib2","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"bib3","doi-asserted-by":"publisher","DOI":"10.3115\/1596276.1596307"},{"key":"bib4","unstructured":"Banarescu, Laura, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013. Abstract meaning representation for sembanking. In Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse, pages 178\u2013186, Sofia."},{"key":"bib5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"bib8","unstructured":"Choi, Jinho D. and Andrew McCallum. 2013. Transition-based dependency parsing with selectional branching. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL-13), pages 1052\u20131062, Sofia."},{"key":"bib9","doi-asserted-by":"publisher","DOI":"10.1007\/s11168-006-6327-9"},{"key":"bib10","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"bib11","unstructured":"Covington, Michael A. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the 39th Annual ACM Southeast Conference, pages 95\u2013102, Athens, GA."},{"key":"bib12","doi-asserted-by":"crossref","unstructured":"Damonte, Marco, Shay B. Cohen, and Giorgio Satta. 2017. An incremental parser for abstract meaning representation. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 536\u2013546, Valencia.","DOI":"10.18653\/v1\/E17-1051"},{"key":"bib14","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/S14-2080"},{"key":"bib15","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P14-1134"},{"key":"bib16","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324900002370"},{"key":"bib17","unstructured":"Flickinger, Dan, Yi Zhang, and Valia Kordoni. 2012. Deepbank: A dynamically annotated treebank of the Wall Street Journal. In Proceedings of the 11th International Workshop on Treebanks and Linguistic Theories, pages 85\u201396, Lisbon."},{"key":"bib18","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00170"},{"key":"bib19","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00150"},{"key":"bib20","unstructured":"Hajic, Jan, Eva Hajicov\u00e1, Jarmila Panevov\u00e1, and Petr Sgall. 2012. Announcing Prague Czech-English dependency treebank 2.0. In Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC\u201912), pages 3153\u20133160, Istanbul."},{"key":"bib21","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00158"},{"key":"bib22","unstructured":"Huang, Liang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL-10), pages 1077\u20131086, Uppsala."},{"key":"bib23","unstructured":"Jones, Bevan, Jacob Andreas, Daniel Bauer, Karl Moritz Hermann, and Kevin Knight. 2012. Semantics-based machine translation with hyperedge replacement grammars. In Proceedings of the 24th International Conference on Computational Linguistics (COLING-12), pages 1359\u20131376, Mumbai."},{"key":"bib24","unstructured":"Jones, Bevan K., Sharon Goldwater, and Mark Johnson. 2013. Modeling graph languages with grammars extracted via tree decompositions. In Proceedings of the 11th International Conference on Finite-State Methods and Natural Language Processing (FSMNLP2013), pages 54\u201362, St. Andrews."},{"key":"bib26","unstructured":"Kuhlmann, Marco, Carlos G\u00f3mez-Rodr\u00edguez, and Giorgio Satta. 2011. Dynamic programming algorithms for transition-based dependency parsers. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 673\u2013682, Portland, OR."},{"key":"bib27","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00268"},{"key":"bib28","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S16-1166"},{"key":"bib30","doi-asserted-by":"publisher","DOI":"10.1162\/coli.07-056-R1-07-027"},{"key":"bib31","doi-asserted-by":"crossref","unstructured":"Nivre, Joakim. 2009. Non-projective dependency parsing in expected linear time. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 351\u2013359, Singapore.","DOI":"10.3115\/1687878.1687929"},{"key":"bib32","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S15-2153"},{"key":"bib33","doi-asserted-by":"publisher","DOI":"10.1162\/0891201053630264"},{"key":"bib34","doi-asserted-by":"crossref","unstructured":"Peng, Xiaochang, Linfeng Song, and Daniel Gildea. 2015. A synchronous hyperedge replacement grammar based approach for AMR parsing. In Proceedings of the Nineteenth Conference on Computational Natural Language Learning (CoNLL-15), pages 731\u2013739, Beijing.","DOI":"10.18653\/v1\/K15-1004"},{"key":"bib35","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/N15-1068"},{"key":"bib36","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/D14-1048"},{"key":"bib37","doi-asserted-by":"crossref","unstructured":"Ribeyre, Corentin, \u00c9ric Villemonte de La Clergerie, and Djam\u00e9 Seddah. 2015. Because syntax does matter: Improving predicate-argument structures parsing using syntactic features. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-15), pages 64\u201374, Denver, CO.","DOI":"10.3115\/v1\/N15-1007"},{"key":"bib38","doi-asserted-by":"publisher","DOI":"10.3115\/1599081.1599176"},{"key":"bib39","unstructured":"Titov, Ivan, James Henderson, Paola Merlo, and Gabriele Musillo. 2009. Online graph planarisation for synchronous parsing of semantic and syntactic dependencies. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-09), pages 1562\u20131567, Pasadena, CA."},{"key":"bib40","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/N15-1040"},{"key":"bib41","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D16-1065"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:28:11Z","timestamp":1615584491000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/44\/1\/85-118\/1590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.1162\/COLI_a_00308"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00308","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3]]}}}