<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="pitler-etal-2013-finding">
    <titleInfo>
        <title>Finding Optimal 1-Endpoint-Crossing Trees</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Emily</namePart>
        <namePart type="family">Pitler</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Sampath</namePart>
        <namePart type="family">Kannan</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Mitchell</namePart>
        <namePart type="family">Marcus</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2013</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <genre authority="bibutilsgt">journal article</genre>
    <relatedItem type="host">
        <titleInfo>
            <title>Transactions of the Association for 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>Dependency parsing algorithms capable of producing the types of crossing dependencies seen in natural language sentences have traditionally been orders of magnitude slower than algorithms for projective trees. For 95.8–99.8% of dependency parses in various natural language treebanks, whenever an edge is crossed, the edges that cross it all have a common vertex. The optimal dependency tree that satisfies this 1-Endpoint-Crossing property can be found with an O(n4) parsing algorithm that recursively combines forests over intervals with one exterior point. 1-Endpoint-Crossing trees also have natural connections to linguistics and another class of graphs that has been studied in NLP.</abstract>
    <identifier type="citekey">pitler-etal-2013-finding</identifier>
    <identifier type="doi">10.1162/tacl_a_00206</identifier>
    <location>
        <url>https://aclanthology.org/Q13-1002</url>
    </location>
    <part>
        <date>2013</date>
        <detail type="volume"><number>1</number></detail>
        <extent unit="page">
            <start>13</start>
            <end>24</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Journal Article
%T Finding Optimal 1-Endpoint-Crossing Trees
%A Pitler, Emily
%A Kannan, Sampath
%A Marcus, Mitchell
%J Transactions of the Association for Computational Linguistics
%D 2013
%V 1
%I MIT Press
%C Cambridge, MA
%F pitler-etal-2013-finding
%X Dependency parsing algorithms capable of producing the types of crossing dependencies seen in natural language sentences have traditionally been orders of magnitude slower than algorithms for projective trees. For 95.8–99.8% of dependency parses in various natural language treebanks, whenever an edge is crossed, the edges that cross it all have a common vertex. The optimal dependency tree that satisfies this 1-Endpoint-Crossing property can be found with an O(n4) parsing algorithm that recursively combines forests over intervals with one exterior point. 1-Endpoint-Crossing trees also have natural connections to linguistics and another class of graphs that has been studied in NLP.
%R 10.1162/tacl_a_00206
%U https://aclanthology.org/Q13-1002
%U https://doi.org/10.1162/tacl_a_00206
%P 13-24

Markdown (Informal)

[Finding Optimal 1-Endpoint-Crossing Trees](https://aclanthology.org/Q13-1002) (Pitler et al., TACL 2013)

• Finding Optimal 1-Endpoint-Crossing Trees (Pitler et al., TACL 2013)

ACL

• Emily Pitler, Sampath Kannan, and Mitchell Marcus. 2013. Finding Optimal 1-Endpoint-Crossing Trees. Transactions of the Association for Computational Linguistics, 1:13–24.