Abstract
A key problem in processing graph-based meaning representations is graph parsing, i.e. computing all possible derivations of a given graph according to a (competence) grammar. We demonstrate, for the first time, that exact graph parsing can be efficient for large graphs and with large Hyperedge Replacement Grammars (HRGs). The advance is achieved by exploiting locality as terminal edge-adjacency in HRG rules. In particular, we highlight the importance of 1) a terminal edge-first parsing strategy, 2) a categorization of a subclass of HRG, i.e. what we call Weakly Regular Graph Grammar, and 3) distributing argument-structures to both lexical and phrasal rules.- Anthology ID:
- 2020.acl-main.377
- Volume:
- Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics
- Month:
- July
- Year:
- 2020
- Address:
- Online
- Editors:
- Dan Jurafsky, Joyce Chai, Natalie Schluter, Joel Tetreault
- Venue:
- ACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 4100–4110
- Language:
- URL:
- https://aclanthology.org/2020.acl-main.377
- DOI:
- 10.18653/v1/2020.acl-main.377
- Cite (ACL):
- Yajie Ye and Weiwei Sun. 2020. Exact yet Efficient Graph Parsing, Bi-directional Locality and the Constructivist Hypothesis. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4100–4110, Online. Association for Computational Linguistics.
- Cite (Informal):
- Exact yet Efficient Graph Parsing, Bi-directional Locality and the Constructivist Hypothesis (Ye & Sun, ACL 2020)
- PDF:
- https://preview.aclanthology.org/landing_page/2020.acl-main.377.pdf