<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="schiffer-etal-2022-tractable">
    <titleInfo>
        <title>Tractable Parsing for CCGs of Bounded Degree</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Lena</namePart>
        <namePart type="given">Katharina</namePart>
        <namePart type="family">Schiffer</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>
    <name type="personal">
        <namePart type="given">Giorgio</namePart>
        <namePart type="family">Satta</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2022-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>Unlike other mildly context-sensitive formalisms, Combinatory Categorial Grammar (CCG) cannot be parsed in polynomial time when the size of the grammar is taken into account. Refining this result, we show that the parsing complexity of CCG is exponential only in the maximum degree of composition. When that degree is fixed, parsing can be carried out in polynomial time. Our finding is interesting from a linguistic perspective because a bounded degree of composition has been suggested as a universal constraint on natural language grammar. Moreover, ours is the first complexity result for a version of CCG that includes substitution rules, which are used in practical grammars but have been ignored in theoretical work.</abstract>
    <identifier type="citekey">schiffer-etal-2022-tractable</identifier>
    <identifier type="doi">10.1162/coli_a_00441</identifier>
    <location>
        <url>https://aclanthology.org/2022.cl-3.4</url>
    </location>
    <part>
        <date>2022-09</date>
        <detail type="volume"><number>48</number></detail>
        <detail type="issue"><number>3</number></detail>
        <extent unit="page">
            <start>593</start>
            <end>633</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Journal Article
%T Tractable Parsing for CCGs of Bounded Degree
%A Schiffer, Lena Katharina
%A Kuhlmann, Marco
%A Satta, Giorgio
%J Computational Linguistics
%D 2022
%8 September
%V 48
%N 3
%I MIT Press
%C Cambridge, MA
%F schiffer-etal-2022-tractable
%X Unlike other mildly context-sensitive formalisms, Combinatory Categorial Grammar (CCG) cannot be parsed in polynomial time when the size of the grammar is taken into account. Refining this result, we show that the parsing complexity of CCG is exponential only in the maximum degree of composition. When that degree is fixed, parsing can be carried out in polynomial time. Our finding is interesting from a linguistic perspective because a bounded degree of composition has been suggested as a universal constraint on natural language grammar. Moreover, ours is the first complexity result for a version of CCG that includes substitution rules, which are used in practical grammars but have been ignored in theoretical work.
%R 10.1162/coli_a_00441
%U https://aclanthology.org/2022.cl-3.4
%U https://doi.org/10.1162/coli_a_00441
%P 593-633

Markdown (Informal)

[Tractable Parsing for CCGs of Bounded Degree](https://aclanthology.org/2022.cl-3.4) (Schiffer et al., CL 2022)

• Tractable Parsing for CCGs of Bounded Degree (Schiffer et al., CL 2022)

ACL

• Lena Katharina Schiffer, Marco Kuhlmann, and Giorgio Satta. 2022. Tractable Parsing for CCGs of Bounded Degree. Computational Linguistics, 48(3):593–633.