@article{bjorklund-etal-2023-generation,
title = "Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies",
author = {Bj{\"o}rklund, Johanna and
Drewes, Frank and
Jonsson, Anna},
journal = "Computational Linguistics",
volume = "49",
number = "4",
month = dec,
year = "2023",
address = "Cambridge, MA",
publisher = "MIT Press",
url = "https://aclanthology.org/2023.cl-4.3",
doi = "10.1162/coli_a_00488",
pages = "841--882",
abstract = "Graph-based semantic representations are popular in natural language processing, where it is often convenient to model linguistic concepts as nodes and relations as edges between them. Several attempts have been made to find a generative device that is sufficiently powerful to describe languages of semantic graphs, while at the same allowing efficient parsing. We contribute to this line of work by introducing graph extension grammar, a variant of the contextual hyperedge replacement grammars proposed by Hoffmann et al. Contextual hyperedge replacement can generate graphs with non-structural reentrancies, a type of node-sharing that is very common in formalisms such as abstract meaning representation, but that context-free types of graph grammars cannot model. To provide our formalism with a way to place reentrancies in a linguistically meaningful way, we endow rules with logical formulas in counting monadic second-order logic. We then present a parsing algorithm and show as our main result that this algorithm runs in polynomial time on graph languages generated by a subclass of our grammars, the so-called local graph extension grammars.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="bjorklund-etal-2023-generation">
<titleInfo>
<title>Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies</title>
</titleInfo>
<name type="personal">
<namePart type="given">Johanna</namePart>
<namePart type="family">Björklund</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Frank</namePart>
<namePart type="family">Drewes</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Anna</namePart>
<namePart type="family">Jonsson</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2023-12</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<genre authority="bibutilsgt">journal article</genre>
<relatedItem type="host">
<titleInfo>
<title>Computational Linguistics</title>
</titleInfo>
<originInfo>
<issuance>continuing</issuance>
<publisher>MIT Press</publisher>
<place>
<placeTerm type="text">Cambridge, MA</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">periodical</genre>
<genre authority="bibutilsgt">academic journal</genre>
</relatedItem>
<abstract>Graph-based semantic representations are popular in natural language processing, where it is often convenient to model linguistic concepts as nodes and relations as edges between them. Several attempts have been made to find a generative device that is sufficiently powerful to describe languages of semantic graphs, while at the same allowing efficient parsing. We contribute to this line of work by introducing graph extension grammar, a variant of the contextual hyperedge replacement grammars proposed by Hoffmann et al. Contextual hyperedge replacement can generate graphs with non-structural reentrancies, a type of node-sharing that is very common in formalisms such as abstract meaning representation, but that context-free types of graph grammars cannot model. To provide our formalism with a way to place reentrancies in a linguistically meaningful way, we endow rules with logical formulas in counting monadic second-order logic. We then present a parsing algorithm and show as our main result that this algorithm runs in polynomial time on graph languages generated by a subclass of our grammars, the so-called local graph extension grammars.</abstract>
<identifier type="citekey">bjorklund-etal-2023-generation</identifier>
<identifier type="doi">10.1162/coli_a_00488</identifier>
<location>
<url>https://aclanthology.org/2023.cl-4.3</url>
</location>
<part>
<date>2023-12</date>
<detail type="volume"><number>49</number></detail>
<detail type="issue"><number>4</number></detail>
<extent unit="page">
<start>841</start>
<end>882</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Journal Article
%T Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies
%A Björklund, Johanna
%A Drewes, Frank
%A Jonsson, Anna
%J Computational Linguistics
%D 2023
%8 December
%V 49
%N 4
%I MIT Press
%C Cambridge, MA
%F bjorklund-etal-2023-generation
%X Graph-based semantic representations are popular in natural language processing, where it is often convenient to model linguistic concepts as nodes and relations as edges between them. Several attempts have been made to find a generative device that is sufficiently powerful to describe languages of semantic graphs, while at the same allowing efficient parsing. We contribute to this line of work by introducing graph extension grammar, a variant of the contextual hyperedge replacement grammars proposed by Hoffmann et al. Contextual hyperedge replacement can generate graphs with non-structural reentrancies, a type of node-sharing that is very common in formalisms such as abstract meaning representation, but that context-free types of graph grammars cannot model. To provide our formalism with a way to place reentrancies in a linguistically meaningful way, we endow rules with logical formulas in counting monadic second-order logic. We then present a parsing algorithm and show as our main result that this algorithm runs in polynomial time on graph languages generated by a subclass of our grammars, the so-called local graph extension grammars.
%R 10.1162/coli_a_00488
%U https://aclanthology.org/2023.cl-4.3
%U https://doi.org/10.1162/coli_a_00488
%P 841-882
Markdown (Informal)
[Generation and Polynomial Parsing of Graph Languages with Non-Structural Reentrancies](https://aclanthology.org/2023.cl-4.3) (Björklund et al., CL 2023)
ACL