{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T03:43:20Z","timestamp":1648957400703},"reference-count":40,"publisher":"MIT Press - Journals","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2019,6]]},"abstract":"<jats:p> We present algorithms for extracting Hyperedge Replacement Grammar (HRG) rules from a graph along with a vertex order. Our algorithms are based on finding a tree decomposition of smallest width, relative to the vertex order, and then extracting one rule for each node in this structure. The assumption of a fixed order for the vertices of the input graph makes it possible to solve the problem in polynomial time, in contrast to the fact that the problem of finding optimal tree decompositions for a graph is NP-hard. We also present polynomial-time algorithms for parsing based on our HRGs, where the input is a vertex sequence and the output is a graph structure. The intended application of our algorithms is grammar extraction and parsing for semantic representation of natural language. We apply our algorithms to data annotated with Abstract Meaning Representations and report on the characteristics of the resulting grammars. <\/jats:p>","DOI":"10.1162\/coli_a_00350","type":"journal-article","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T18:09:55Z","timestamp":1553105395000},"page":"339-379","source":"Crossref","is-referenced-by-count":0,"title":["Ordered Tree Decomposition for HRG Rule Extraction"],"prefix":"10.1162","volume":"45","author":[{"given":"Daniel","family":"Gildea","sequence":"first","affiliation":[{"name":"University of Rochester, Computer Science Department."}]},{"given":"Giorgio","family":"Satta","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Padova, Dipartimento di Ingegneria dell\u2019Informazione."}]},{"given":"Xiaochang","family":"Peng","sequence":"additional","affiliation":[{"name":"University of Rochester, Computer Science Department."}]}],"member":"281","reference":[{"key":"bib1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90070-3"},{"key":"bib2","volume-title":"The Theory of Parsing, Translation, and Compiling","volume":"1","author":"Aho Albert V.","year":"1972"},{"key":"bib3","first-page":"178","volume-title":"Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse","author":"Banarescu Laura","year":"2013"},{"key":"bib4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9_40"},{"key":"bib5","first-page":"924","volume-title":"Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)","author":"Chiang David","year":"2013"},{"key":"bib6","doi-asserted-by":"publisher","DOI":"10.3115\/981863.981888"},{"key":"bib7","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/E17-1051"},{"key":"bib8","author":"Dohare Shibhansh","year":"2017","journal-title":"CoRR"},{"key":"bib9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21145-9_2"},{"key":"bib10","doi-asserted-by":"publisher","DOI":"10.1142\/9789812384720_0002"},{"key":"bib11","doi-asserted-by":"publisher","DOI":"10.3115\/992628.992688"},{"key":"bib12","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P14-1134"},{"key":"bib13","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00308"},{"key":"bib14","first-page":"77","volume-title":"Advances in Computers","volume":"14","author":"Graham S. L.","year":"1976"},{"key":"bib15","first-page":"1077","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Lignuistics (ACL-10)","author":"Huang Liang","year":"2010"},{"key":"bib16","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/P16-1025"},{"key":"bib17","first-page":"1359","volume-title":"Proceedings of the 24th International Conference on Computational Linguistics (COLING-12)","author":"Jones Bevan","year":"2012"},{"key":"bib18","first-page":"54","volume-title":"Proceedings of the 11th International Conference on Finite-State Methods and Natural Language Processing (FSMNLP2013)","author":"Jones Bevan K.","year":"2013"},{"key":"bib19","first-page":"1905","volume-title":"Proceedings of the National Conference on Artificial Intelligence (AAAI-18)","author":"Khashabi Daniel","year":"2018"},{"key":"bib20","doi-asserted-by":"publisher","DOI":"10.3115\/1218955.1219016"},{"key":"bib21","doi-asserted-by":"publisher","DOI":"10.2200\/S00169ED1V01Y200901HLT002"},{"key":"bib22","first-page":"673","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies","author":"Kuhlmann Marco","year":"2011"},{"key":"bib23","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00158"},{"key":"bib24","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00268"},{"key":"bib25","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90051-5"},{"key":"bib26","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0026094"},{"key":"bib27","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289017"},{"key":"bib28","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/N15-1114"},{"key":"bib29","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S16-1166"},{"key":"bib30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39886-8_28"},{"key":"bib31","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S15-2153"},{"key":"bib32","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/S14-2008"},{"key":"bib33","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/K15-1004"},{"key":"bib34","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/P18-1171"},{"key":"bib35","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/D14-1048"},{"key":"bib36","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/W17-2315"},{"key":"bib37","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S15-1031"},{"key":"bib38","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D16-1112"},{"key":"bib39","doi-asserted-by":"publisher","DOI":"10.3115\/1219840.1219913"},{"key":"bib40","doi-asserted-by":"publisher","DOI":"10.1145\/3107411.3107426"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/coli_a_00350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:28:23Z","timestamp":1615584503000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/45\/2\/339-379\/1635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["10.1162\/coli_a_00350"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00350","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6]]}}}