@inproceedings{branco-2018-computational,
title = "Computational Complexity of Natural Languages: A Reasoned Overview",
author = "Branco, Ant{\'o}nio",
editor = "Becerra-Bonache, Leonor and
Jim{\'e}nez-L{\'o}pez, M. Dolores and
Mart{\'\i}n-Vide, Carlos and
Torrens-Urrutia, Adri{\`a}",
booktitle = "Proceedings of the Workshop on Linguistic Complexity and Natural Language Processing",
month = aug,
year = "2018",
address = "Santa Fe, New-Mexico",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/W18-4602",
pages = "10--19",
abstract = "There has been an upsurge of research interest in natural language complexity. As this interest will benefit from being informed by established contributions in this area, this paper presents a reasoned overview of central results concerning the computational complexity of natural language parsing. This overview also seeks to help to understand why, contrary to recent and widespread assumptions, it is by no means sufficient that an agent handles sequences of items under a pattern $a^n b^n$ or under a pattern $a^n b^m c^n d^m$ to ascertain ipso facto that this is the result of at least an underlying context-free grammar or an underlying context-sensitive grammar, respectively. In addition, it seeks to help to understand why it is also not sufficient that an agent handles sequences of items under a pattern $a^n b^n$ for it to be deemed as having a cognitive capacity of higher computational complexity.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="branco-2018-computational">
<titleInfo>
<title>Computational Complexity of Natural Languages: A Reasoned Overview</title>
</titleInfo>
<name type="personal">
<namePart type="given">António</namePart>
<namePart type="family">Branco</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2018-08</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the Workshop on Linguistic Complexity and Natural Language Processing</title>
</titleInfo>
<name type="personal">
<namePart type="given">Leonor</namePart>
<namePart type="family">Becerra-Bonache</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">M</namePart>
<namePart type="given">Dolores</namePart>
<namePart type="family">Jiménez-López</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Carlos</namePart>
<namePart type="family">Martín-Vide</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Adrià</namePart>
<namePart type="family">Torrens-Urrutia</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Santa Fe, New-Mexico</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<abstract>There has been an upsurge of research interest in natural language complexity. As this interest will benefit from being informed by established contributions in this area, this paper presents a reasoned overview of central results concerning the computational complexity of natural language parsing. This overview also seeks to help to understand why, contrary to recent and widespread assumptions, it is by no means sufficient that an agent handles sequences of items under a pattern aⁿ bⁿ or under a pattern aⁿ b^m cⁿ d^m to ascertain ipso facto that this is the result of at least an underlying context-free grammar or an underlying context-sensitive grammar, respectively. In addition, it seeks to help to understand why it is also not sufficient that an agent handles sequences of items under a pattern aⁿ bⁿ for it to be deemed as having a cognitive capacity of higher computational complexity.</abstract>
<identifier type="citekey">branco-2018-computational</identifier>
<location>
<url>https://aclanthology.org/W18-4602</url>
</location>
<part>
<date>2018-08</date>
<extent unit="page">
<start>10</start>
<end>19</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Computational Complexity of Natural Languages: A Reasoned Overview
%A Branco, António
%Y Becerra-Bonache, Leonor
%Y Jiménez-López, M. Dolores
%Y Martín-Vide, Carlos
%Y Torrens-Urrutia, Adrià
%S Proceedings of the Workshop on Linguistic Complexity and Natural Language Processing
%D 2018
%8 August
%I Association for Computational Linguistics
%C Santa Fe, New-Mexico
%F branco-2018-computational
%X There has been an upsurge of research interest in natural language complexity. As this interest will benefit from being informed by established contributions in this area, this paper presents a reasoned overview of central results concerning the computational complexity of natural language parsing. This overview also seeks to help to understand why, contrary to recent and widespread assumptions, it is by no means sufficient that an agent handles sequences of items under a pattern aⁿ bⁿ or under a pattern aⁿ b^m cⁿ d^m to ascertain ipso facto that this is the result of at least an underlying context-free grammar or an underlying context-sensitive grammar, respectively. In addition, it seeks to help to understand why it is also not sufficient that an agent handles sequences of items under a pattern aⁿ bⁿ for it to be deemed as having a cognitive capacity of higher computational complexity.
%U https://aclanthology.org/W18-4602
%P 10-19
Markdown (Informal)
[Computational Complexity of Natural Languages: A Reasoned Overview](https://aclanthology.org/W18-4602) (Branco, 2018)
ACL