@article{kuhlmann-etal-2018-complexity,
title = "On the Complexity of {CCG} Parsing",
author = "Kuhlmann, Marco and
Satta, Giorgio and
Jonsson, Peter",
journal = "Computational Linguistics",
volume = "44",
number = "3",
month = sep,
year = "2018",
address = "Cambridge, MA",
publisher = "MIT Press",
url = "https://aclanthology.org/J18-3004",
doi = "10.1162/coli_a_00324",
pages = "447--482",
abstract = "We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir (1994). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir (1994) apart from weakly equivalent formalisms such as Tree Adjoining Grammar, for which parsing can be performed in time polynomial in the combined size of grammar and input sentence. Our results contribute to a refined understanding of the class of mildly context-sensitive grammars, and inform the search for new, mildly context-sensitive versions of CCG.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="kuhlmann-etal-2018-complexity">
<titleInfo>
<title>On the Complexity of CCG Parsing</title>
</titleInfo>
<name type="personal">
<namePart type="given">Marco</namePart>
<namePart type="family">Kuhlmann</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">Peter</namePart>
<namePart type="family">Jonsson</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2018-09</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 study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir (1994). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir (1994) apart from weakly equivalent formalisms such as Tree Adjoining Grammar, for which parsing can be performed in time polynomial in the combined size of grammar and input sentence. Our results contribute to a refined understanding of the class of mildly context-sensitive grammars, and inform the search for new, mildly context-sensitive versions of CCG.</abstract>
<identifier type="citekey">kuhlmann-etal-2018-complexity</identifier>
<identifier type="doi">10.1162/coli_a_00324</identifier>
<location>
<url>https://aclanthology.org/J18-3004</url>
</location>
<part>
<date>2018-09</date>
<detail type="volume"><number>44</number></detail>
<detail type="issue"><number>3</number></detail>
<extent unit="page">
<start>447</start>
<end>482</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Journal Article
%T On the Complexity of CCG Parsing
%A Kuhlmann, Marco
%A Satta, Giorgio
%A Jonsson, Peter
%J Computational Linguistics
%D 2018
%8 September
%V 44
%N 3
%I MIT Press
%C Cambridge, MA
%F kuhlmann-etal-2018-complexity
%X We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir (1994). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir (1994) apart from weakly equivalent formalisms such as Tree Adjoining Grammar, for which parsing can be performed in time polynomial in the combined size of grammar and input sentence. Our results contribute to a refined understanding of the class of mildly context-sensitive grammars, and inform the search for new, mildly context-sensitive versions of CCG.
%R 10.1162/coli_a_00324
%U https://aclanthology.org/J18-3004
%U https://doi.org/10.1162/coli_a_00324
%P 447-482
Markdown (Informal)
[On the Complexity of CCG Parsing](https://aclanthology.org/J18-3004) (Kuhlmann et al., CL 2018)
ACL