<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="gildea-etal-2019-ordered">
    <titleInfo>
        <title>Ordered Tree Decomposition for HRG Rule Extraction</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Daniel</namePart>
        <namePart type="family">Gildea</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Giorgio</namePart>
        <namePart type="family">Satta</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Xiaochang</namePart>
        <namePart type="family">Peng</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2019-06</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>We present algorithms for extracting Hyperedge Replacement Grammar (HRG) rules from a graph along with a vertex order. Our algorithms are based on finding a tree decomposition of smallest width, relative to the vertex order, and then extracting one rule for each node in this structure. The assumption of a fixed order for the vertices of the input graph makes it possible to solve the problem in polynomial time, in contrast to the fact that the problem of finding optimal tree decompositions for a graph is NP-hard. We also present polynomial-time algorithms for parsing based on our HRGs, where the input is a vertex sequence and the output is a graph structure. The intended application of our algorithms is grammar extraction and parsing for semantic representation of natural language. We apply our algorithms to data annotated with Abstract Meaning Representations and report on the characteristics of the resulting grammars.</abstract>
    <identifier type="citekey">gildea-etal-2019-ordered</identifier>
    <identifier type="doi">10.1162/coli_a_00350</identifier>
    <location>
        <url>https://aclanthology.org/J19-2005</url>
    </location>
    <part>
        <date>2019-06</date>
        <detail type="volume"><number>45</number></detail>
        <detail type="issue"><number>2</number></detail>
        <extent unit="page">
            <start>339</start>
            <end>379</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Journal Article
%T Ordered Tree Decomposition for HRG Rule Extraction
%A Gildea, Daniel
%A Satta, Giorgio
%A Peng, Xiaochang
%J Computational Linguistics
%D 2019
%8 June
%V 45
%N 2
%I MIT Press
%C Cambridge, MA
%F gildea-etal-2019-ordered
%X We present algorithms for extracting Hyperedge Replacement Grammar (HRG) rules from a graph along with a vertex order. Our algorithms are based on finding a tree decomposition of smallest width, relative to the vertex order, and then extracting one rule for each node in this structure. The assumption of a fixed order for the vertices of the input graph makes it possible to solve the problem in polynomial time, in contrast to the fact that the problem of finding optimal tree decompositions for a graph is NP-hard. We also present polynomial-time algorithms for parsing based on our HRGs, where the input is a vertex sequence and the output is a graph structure. The intended application of our algorithms is grammar extraction and parsing for semantic representation of natural language. We apply our algorithms to data annotated with Abstract Meaning Representations and report on the characteristics of the resulting grammars.
%R 10.1162/coli_a_00350
%U https://aclanthology.org/J19-2005
%U https://doi.org/10.1162/coli_a_00350
%P 339-379

Markdown (Informal)

[Ordered Tree Decomposition for HRG Rule Extraction](https://aclanthology.org/J19-2005) (Gildea et al., CL 2019)

• Ordered Tree Decomposition for HRG Rule Extraction (Gildea et al., CL 2019)

ACL

• Daniel Gildea, Giorgio Satta, and Xiaochang Peng. 2019. Ordered Tree Decomposition for HRG Rule Extraction. Computational Linguistics, 45(2):339–379.