The Importance of Rule Restrictions in CCG
Kuhlmann, Marco and Koller, Alexander and Satta, Giorgio

Article Structure

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.

Introduction

Combinatory Categorial Grammar (CCG) (Steedman, 2001; Steedman and Baldridge, 2010) is an expressive grammar formalism with formal roots in combinatory logic (Curry et al., 1958) and links to the type-logical tradition of categorial grammar (Moortgat, 1997).

Combinatory Categorial Grammar

We start by providing formal definitions for categories, syntactic rules, and grammars, and then discuss the relevance of rule restrictions for CCG.

The Generative Capacity of Pure CCG

We will now develop a formal argument showing that rule restrictions increase the weak generative capacity of CCG.

Multi-Modal CCG

We now extend Theorem 1 to multi-modal CCG.

Conclusion

In this paper, we have shown that the weak generative capacity of pure CCG and even pure B&K—CCG crucially depends on the ability to restrict the application of individual rules.

Topics

CCG

Appears in 73 sentences as: (1) CCG (83) CCG’ (1)
In The Importance of Rule Restrictions in CCG
  1. 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.
    Page 1, “Abstract”
  2. In this paper, we show that the weak generative capacity of this ‘pure’ form of CCG is strictly smaller than that of CCG with gram-mar-specific rules, and of other mildly con-text-sensitive grammar formalisms, including Tree Adjoining Grammar (TAG).
    Page 1, “Abstract”
  3. Our result also carries over to a multi-modal extension of CCG .
    Page 1, “Abstract”
  4. Combinatory Categorial Grammar ( CCG ) (Steedman, 2001; Steedman and Baldridge, 2010) is an expressive grammar formalism with formal roots in combinatory logic (Curry et al., 1958) and links to the type-logical tradition of categorial grammar (Moortgat, 1997).
    Page 1, “Introduction”
  5. It is well-known that CCG can generate languages that are not context-free (which is necessary to capture natural languages), but can still be parsed in polynomial time.
    Page 1, “Introduction”
  6. Specifically, Vij ay-Shanker and Weir (1994) identified a version of CCG that is weakly equivalent to Tree Adjoining Grammar (TAG) (Joshi and Schabes, 1997) and other mildly context-sensitive grammar formalisms, and can generate non-context—free languages such as anbnc”.
    Page 1, “Introduction”
  7. The generative capacity of CCG is commonly attributed to its flexible composition rules, which allow it to model more complex word orders that context-free grammar can.
    Page 1, “Introduction”
  8. The discussion of the (weak and strong) generative capacity of CCG and TAG has recently been revived (Hockenmaier and Young, 2008; Koller and Kuhlmann, 2009).
    Page 1, “Introduction”
  9. This shows that the generative capacity of at least first-order CCG crucially relies on its ability to restrict rule instantiations, and is at odds with the general conception of CCG as a fully lexicalized formalism, in which all grammars use one and the same set of universal rules.
    Page 1, “Introduction”
  10. A question then is whether the result carries over to pure CCG with higher-order categories.
    Page 1, “Introduction”
  11. In this paper, we answer this question to the positive: We show that the weak generative capacity of general pure CCG is still strictly smaller than that of the formalism considered by Vij ay-Shanker and Weir (1994); composition rules can only achieve their full expressive potential if their use can be restricted.
    Page 1, “Introduction”

See all papers in Proc. ACL 2010 that mention CCG.

See all papers in Proc. ACL that mention CCG.

Back to top.

lexicalized

Appears in 5 sentences as: lexicalized (5)
In The Importance of Rule Restrictions in CCG
  1. 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.
    Page 1, “Abstract”
  2. This shows that the generative capacity of at least first-order CCG crucially relies on its ability to restrict rule instantiations, and is at odds with the general conception of CCG as a fully lexicalized formalism, in which all grammars use one and the same set of universal rules.
    Page 1, “Introduction”
  3. This means that word order in CCG cannot be fully lexicalized with the current formal tools; some ordering constraints must be specified via language-specific combination rules and not in lexicon entries.
    Page 2, “Introduction”
  4. This is what makes pure CCG a lexicalized grammar formalism (Steedman and Baldridge, 2010).
    Page 3, “Combinatory Categorial Grammar”
  5. This means that these formalisms cannot be fully lexicalized , in the sense that certain languages can only be described by selecting language-specific rules.
    Page 9, “Conclusion”

See all papers in Proc. ACL 2010 that mention lexicalized.

See all papers in Proc. ACL that mention lexicalized.

Back to top.

natural languages

Appears in 4 sentences as: natural language (1) natural languages (4)
In The Importance of Rule Restrictions in CCG
  1. It is well-known that CCG can generate languages that are not context-free (which is necessary to capture natural languages ), but can still be parsed in polynomial time.
    Page 1, “Introduction”
  2. On the other hand, as pure multi-modal CCG has been successfully applied to model the syntax of a variety of natural languages, another way to read our results is as contributions to a discussion about the exact expressiveness needed to model natural language .
    Page 2, “Introduction”
  3. Of course, at the end of the day, the issue that is more relevant to computational linguistics than a formalism’s ability to generate artificial languages such as L3 is how useful it is for modeling natural languages .
    Page 9, “Conclusion”
  4. In this sense, our formal result can also be understood as a contribution to a discussion about the expressive power that is needed to model natural languages .
    Page 9, “Conclusion”

See all papers in Proc. ACL 2010 that mention natural languages.

See all papers in Proc. ACL that mention natural languages.

Back to top.

word order

Appears in 4 sentences as: word order (3) word orders (1)
In The Importance of Rule Restrictions in CCG
  1. The generative capacity of CCG is commonly attributed to its flexible composition rules, which allow it to model more complex word orders that context-free grammar can.
    Page 1, “Introduction”
  2. This means that word order in CCG cannot be fully lexicalized with the current formal tools; some ordering constraints must be specified via language-specific combination rules and not in lexicon entries.
    Page 2, “Introduction”
  3. Consider the examples in Figure 2: It is because we cannot ensure that the bs finish combining with the other bs before combining with the cs that the undesirable word order in Figure 2b has a derivation.
    Page 5, “The Generative Capacity of Pure CCG”
  4. Slash types make the derivation process sensitive to word order by restricting the use of compositions to categories with the appropriate type, and the transformation rules permute the order of the words in the string.
    Page 8, “Multi-Modal CCG”

See all papers in Proc. ACL 2010 that mention word order.

See all papers in Proc. ACL that mention word order.

Back to top.

PDF available from www.aclweb.org.
Send us an email