<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="kurtz-kuhlmann-2017-exploiting">
    <titleInfo>
        <title>Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Robin</namePart>
        <namePart type="family">Kurtz</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Marco</namePart>
        <namePart type="family">Kuhlmann</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2017-09</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 15th International Conference on Parsing Technologies</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Yusuke</namePart>
            <namePart type="family">Miyao</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Kenji</namePart>
            <namePart type="family">Sagae</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Pisa, Italy</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <abstract>Deep dependency parsing can be cast as the search for maximum acyclic subgraphs in weighted digraphs. Because this search problem is intractable in the general case, we consider its restriction to the class of 1-endpoint-crossing (1ec) graphs, which has high coverage on standard data sets. Our main contribution is a characterization of 1ec graphs as a subclass of the graphs with pagenumber at most 3. Building on this we show how to extend an existing parsing algorithm for 1-endpoint-crossing trees to the full class. While the runtime complexity of the extended algorithm is polynomial in the length of the input sentence, it features a large constant, which poses a challenge for practical implementations.</abstract>
    <identifier type="citekey">kurtz-kuhlmann-2017-exploiting</identifier>
    <location>
        <url>https://aclanthology.org/W17-6312</url>
    </location>
    <part>
        <date>2017-09</date>
        <extent unit="page">
            <start>78</start>
            <end>87</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs
%A Kurtz, Robin
%A Kuhlmann, Marco
%Y Miyao, Yusuke
%Y Sagae, Kenji
%S Proceedings of the 15th International Conference on Parsing Technologies
%D 2017
%8 September
%I Association for Computational Linguistics
%C Pisa, Italy
%F kurtz-kuhlmann-2017-exploiting
%X Deep dependency parsing can be cast as the search for maximum acyclic subgraphs in weighted digraphs. Because this search problem is intractable in the general case, we consider its restriction to the class of 1-endpoint-crossing (1ec) graphs, which has high coverage on standard data sets. Our main contribution is a characterization of 1ec graphs as a subclass of the graphs with pagenumber at most 3. Building on this we show how to extend an existing parsing algorithm for 1-endpoint-crossing trees to the full class. While the runtime complexity of the extended algorithm is polynomial in the length of the input sentence, it features a large constant, which poses a challenge for practical implementations.
%U https://aclanthology.org/W17-6312
%P 78-87

Markdown (Informal)

[Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs](https://aclanthology.org/W17-6312) (Kurtz & Kuhlmann, IWPT 2017)

• Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs (Kurtz & Kuhlmann, IWPT 2017)

ACL

• Robin Kurtz and Marco Kuhlmann. 2017. Exploiting Structure in Parsing to 1-Endpoint-Crossing Graphs. In Proceedings of the 15th International Conference on Parsing Technologies, pages 78–87, Pisa, Italy. Association for Computational Linguistics.