Parsing Graphs with Regular Graph Grammars

Sorcha Gilroy, Adam Lopez, Sebastian Maneth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recently, several datasets have become available which represent natural language phenomena as graphs. Hyperedge Replacement Languages (HRL) have been the focus of much attention as a formalism to represent the graphs in these datasets. Chiang et al. (2013) prove that HRL graphs can be parsed in polynomial time with respect to the size of the input graph. We believe that HRL are more expressive than is necessary to represent semantic graphs and we propose the use of Regular Graph Languages (RGL; Courcelle 1991), which is a subfamily of HRL, as a possible
alternative. We provide a topdown parsing algorithm for RGL that runs in time linear in the size of the input graph.
Original languageEnglish
Title of host publicationProceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017)
PublisherAssociation for Computational Linguistics (ACL)
Pages199-208
Number of pages10
ISBN (Print)978-1-945626-53-1
DOIs
Publication statusPublished - 4 Aug 2017
Event6th Joint Conference on Lexical and Computational Semantics - Vancouver, Canada
Duration: 3 Aug 20174 Aug 2017
https://sites.google.com/site/starsem2017/

Conference

Conference6th Joint Conference on Lexical and Computational Semantics
Abbreviated title*SEM 2017
CountryCanada
CityVancouver
Period3/08/174/08/17
Internet address

Fingerprint

Dive into the research topics of 'Parsing Graphs with Regular Graph Grammars'. Together they form a unique fingerprint.

Cite this