@inproceedings{gilroy-etal-2017-parsing,
title = "Parsing Graphs with Regular Graph Grammars",
author = "Gilroy, Sorcha and
Lopez, Adam and
Maneth, Sebastian",
editor = "Ide, Nancy and
Herbelot, Aur{\'e}lie and
M{\`a}rquez, Llu{\'\i}s",
booktitle = "Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*{SEM} 2017)",
month = aug,
year = "2017",
address = "Vancouver, Canada",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/S17-1024",
doi = "10.18653/v1/S17-1024",
pages = "199--208",
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 top-down parsing algorithm for RGL that runs in time linear in the size of the input graph.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="gilroy-etal-2017-parsing">
<titleInfo>
<title>Parsing Graphs with Regular Graph Grammars</title>
</titleInfo>
<name type="personal">
<namePart type="given">Sorcha</namePart>
<namePart type="family">Gilroy</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Adam</namePart>
<namePart type="family">Lopez</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Sebastian</namePart>
<namePart type="family">Maneth</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2017-08</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017)</title>
</titleInfo>
<name type="personal">
<namePart type="given">Nancy</namePart>
<namePart type="family">Ide</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Aurélie</namePart>
<namePart type="family">Herbelot</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Lluís</namePart>
<namePart type="family">Màrquez</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Vancouver, Canada</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<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 top-down parsing algorithm for RGL that runs in time linear in the size of the input graph.</abstract>
<identifier type="citekey">gilroy-etal-2017-parsing</identifier>
<identifier type="doi">10.18653/v1/S17-1024</identifier>
<location>
<url>https://aclanthology.org/S17-1024</url>
</location>
<part>
<date>2017-08</date>
<extent unit="page">
<start>199</start>
<end>208</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Parsing Graphs with Regular Graph Grammars
%A Gilroy, Sorcha
%A Lopez, Adam
%A Maneth, Sebastian
%Y Ide, Nancy
%Y Herbelot, Aurélie
%Y Màrquez, Lluís
%S Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017)
%D 2017
%8 August
%I Association for Computational Linguistics
%C Vancouver, Canada
%F gilroy-etal-2017-parsing
%X 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 top-down parsing algorithm for RGL that runs in time linear in the size of the input graph.
%R 10.18653/v1/S17-1024
%U https://aclanthology.org/S17-1024
%U https://doi.org/10.18653/v1/S17-1024
%P 199-208
Markdown (Informal)
[Parsing Graphs with Regular Graph Grammars](https://aclanthology.org/S17-1024) (Gilroy et al., *SEM 2017)
ACL
- Sorcha Gilroy, Adam Lopez, and Sebastian Maneth. 2017. Parsing Graphs with Regular Graph Grammars. In Proceedings of the 6th Joint Conference on Lexical and Computational Semantics (*SEM 2017), pages 199–208, Vancouver, Canada. Association for Computational Linguistics.