The Importance of Rule Restrictions in CCG

Marco Kuhlmann, Alexander Koller, Giorgio SattaACL 2010 · OpenReview

Abstract: Combinatory Categorial Grammar (CCG) is generally construed as a fully lexicalized formalism, where all grammars use one and the same universal set of rules, and cross-linguistic variation is isolated in the lexicon. In this paper, we show that the weak generative capacity of this 'pure' form of CCG is strictly smaller than that of CCG with grammar-specific rules, and of other mildly context-sensitive grammar formalisms, including Tree Adjoining Grammar (TAG). Our result also carries over to a multi-modal extension of CCG.

Introduction: The Lexicalization Ideal

Combinatory Categorial Grammar (CCG) is a prominent formalism in computational linguistics, celebrated for its ability to handle complex natural language phenomena like cross-serial dependencies while remaining computationally efficient. A core philosophical tenet of CCG is that it is "fully lexicalized." In theory, this means the grammar consists of a universal set of combinatory rules—such as application and composition—and all language-specific variation is stored within the lexicon (the dictionary).

The universal set of combinatory rules in CCG, including forward/backward application and harmonic/crossed composition.

However, in practical applications, researchers often find it necessary to impose grammar-specific restrictions on these rules (e.g., "English does not allow forward crossed composition"). This paper investigates whether these restrictions are merely a convenience or a formal necessity for the grammar's expressive power.

Proving the Limits of "Pure" CCG

The authors define "pure" CCG as a version of the formalism that uses a universal set of rules without any grammar-specific bans. To analyze its power, they employ a formal proof technique centered on the Permutation Language Lemma.

  1. Active vs. Inactive Arguments: The proof categorizes arguments in CCG categories based on their role in a derivation.
  2. Derivation Transformation: The authors introduce a system of rewriting rules to "rotate" CCG derivation trees. This transformation aims to "saturate" arguments as early as possible in the process.
  3. Bounded Arity: They demonstrate that in these transformed derivations, the complexity (arity) of any intermediate category remains bounded. This is a critical finding, as it implies that the transformed grammar can be simulated by a simpler Context-Free Grammar (CFG).
  4. Parikh Equivalence: Because the transformation only alters the order of operations (and thus word order) while maintaining the same set of lexical items, the authors show that every language generated by pure CCG is "Parikh-equivalent" to a context-free language.

Key Insight: The Overgeneration Trap

The primary finding is that without rule restrictions, CCG suffers from an "overgeneration trap." If a pure CCG can generate a complex, non-context-free string like $a^n b^n c^n$, it inevitably also generates every "scrambled" permutation of that string.

Derivations from the same grammar: (a) shows the desired string $aaabbbccc$, while (b) shows an unwanted permutation that a pure CCG cannot prevent without explicit rule restrictions.

This means that pure CCG cannot generate the language $a^n b^n c^n$ itself, but only a version of it that includes all possible word-order permutations. Consequently, pure CCG is strictly less powerful than restricted CCG or Tree Adjoining Grammar (TAG).

Implications for Multi-Modal CCG

Multi-Modal CCG (MM-CCG) was developed to address these issues by moving rule restrictions into the lexicon using "slash types." However, the authors prove that their Permutation Language Lemma holds for pure MM-CCG as well. Even with sophisticated slash types, explicit rule restrictions remain necessary to achieve the full expressive potential required for natural language modeling.

Conclusion

This research clarifies the formal hierarchy of grammar formalisms, placing pure CCG in a unique middle ground: more powerful than CFGs but less powerful than the restricted CCGs used in practice. It highlights a fundamental tension in linguistics between the desire for universal, elegant formalisms and the practical necessity of language-specific constraints to capture the precise word-order requirements of human speech.

Summary updated

Abstract

Combinatory Categorial Grammar (CCG) is generally construed as a fully lexicalized formalism, where all grammars use one and the same universal set of rules, and cross-linguistic variation is isolated in the lexicon. In this paper, we show that the weak generative capacity of this 'pure' form of CCG is strictly smaller than that of CCG with grammar-specific rules, and of other mildly context-sensitive grammar formalisms, including Tree Adjoining Grammar (TAG). Our result also carries over to a multi-modal extension of CCG.
BibTeX
@inproceedings{kuhlmann2010importance,
  author = {Marco Kuhlmann and Alexander Koller and Giorgio Satta},
  title = {{The Importance of Rule Restrictions in CCG}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=ryWRLsxd-r},
}
Figure