@inproceedings{corro-2020-span,
title = "Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from {O}(n{\textasciicircum}6) down to {O}(n{\textasciicircum}3)",
author = "Corro, Caio",
editor = "Webber, Bonnie and
Cohn, Trevor and
He, Yulan and
Liu, Yang",
booktitle = "Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)",
month = nov,
year = "2020",
address = "Online",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2020.emnlp-main.219/",
doi = "10.18653/v1/2020.emnlp-main.219",
pages = "2753--2764",
abstract = "We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from O(n{\textasciicircum}6) down to O(n{\textasciicircum}3). The cubic time variant covers 98{\%} of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on German and English treebanks (Negra, Tiger, and DPTB) and report state-of-the-art results in the fully supervised setting. We also experiment with pre-trained word embeddings and Bert-based neural networks."
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="corro-2020-span">
<titleInfo>
<title>Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n⌃6) down to O(n⌃3)</title>
</titleInfo>
<name type="personal">
<namePart type="given">Caio</namePart>
<namePart type="family">Corro</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2020-11</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)</title>
</titleInfo>
<name type="personal">
<namePart type="given">Bonnie</namePart>
<namePart type="family">Webber</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Trevor</namePart>
<namePart type="family">Cohn</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Yulan</namePart>
<namePart type="family">He</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Yang</namePart>
<namePart type="family">Liu</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Online</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<abstract>We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from O(n⌃6) down to O(n⌃3). The cubic time variant covers 98% of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on German and English treebanks (Negra, Tiger, and DPTB) and report state-of-the-art results in the fully supervised setting. We also experiment with pre-trained word embeddings and Bert-based neural networks.</abstract>
<identifier type="citekey">corro-2020-span</identifier>
<identifier type="doi">10.18653/v1/2020.emnlp-main.219</identifier>
<location>
<url>https://aclanthology.org/2020.emnlp-main.219/</url>
</location>
<part>
<date>2020-11</date>
<extent unit="page">
<start>2753</start>
<end>2764</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n⌃6) down to O(n⌃3)
%A Corro, Caio
%Y Webber, Bonnie
%Y Cohn, Trevor
%Y He, Yulan
%Y Liu, Yang
%S Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)
%D 2020
%8 November
%I Association for Computational Linguistics
%C Online
%F corro-2020-span
%X We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from O(n⌃6) down to O(n⌃3). The cubic time variant covers 98% of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on German and English treebanks (Negra, Tiger, and DPTB) and report state-of-the-art results in the fully supervised setting. We also experiment with pre-trained word embeddings and Bert-based neural networks.
%R 10.18653/v1/2020.emnlp-main.219
%U https://aclanthology.org/2020.emnlp-main.219/
%U https://doi.org/10.18653/v1/2020.emnlp-main.219
%P 2753-2764
Markdown (Informal)
[Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(nˆ6) down to O(nˆ3)](https://aclanthology.org/2020.emnlp-main.219/) (Corro, EMNLP 2020)
ACL