Graph Formalisms for Meaning Representations

Adam Lopez, Sorcha Gilroy


Abstract
In this tutorial we will focus on Hyperedge Replacement Languages (HRL; Drewes et al. 1997), a context-free graph rewriting system. HRL are one of the most popular graph formalisms to be studied in NLP (Chiang et al., 2013; Peng et al., 2015; Bauer and Rambow, 2016). We will discuss HRL by formally defining them, studying several examples, discussing their properties, and providing exercises for the tutorial. While HRL have been used in NLP in the past, there is some speculation that they are more expressive than is necessary for graphs representing natural language (Drewes, 2017). Part of our own research has been exploring what restrictions of HRL could yield languages that are more useful for NLP and also those that have desirable properties for NLP models, such as being closed under intersection. With that in mind, we also plan to discuss Regular Graph Languages (RGL; Courcelle 1991), a subfamily of HRL which are closed under intersection. The definition of RGL is relatively simple after being introduced to HRL. We do not plan on discussing any proofs of why RGL are also a subfamily of MSOL, as described in Gilroy et al. (2017b). We will briefly mention the other formalisms shown in Figure 1 such as MSOL and DAGAL but this will focus on their properties rather than any formal definitions.
Anthology ID:
D18-3002
Volume:
Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: Tutorial Abstracts
Month:
October-November
Year:
2018
Address:
Melbourne, Australia
Editors:
Mausam, Lu Wang
Venue:
EMNLP
SIG:
SIGDAT
Publisher:
Association for Computational Linguistics
Note:
Pages:
Language:
URL:
https://aclanthology.org/D18-3002
DOI:
Bibkey:
Cite (ACL):
Adam Lopez and Sorcha Gilroy. 2018. Graph Formalisms for Meaning Representations. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: Tutorial Abstracts, Melbourne, Australia. Association for Computational Linguistics.
Cite (Informal):
Graph Formalisms for Meaning Representations (Lopez & Gilroy, EMNLP 2018)
Copy Citation: