The Importance of Rule Restrictions in CCG

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 534–543, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics The Importance of Rule Restrictions in CCG Marco Kuhlmann Dept. of Linguistics and Philology Uppsala University Uppsala, Sweden Alexander Koller Cluster of Excellence Saarland University Saarbrücken, Germany Giorgio Satta Dept. of Information Engineering University of Padua Padua, Italy 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 gener- ative 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, includ- ing Tree Adjoining Grammar (TAG). Our result also carries over to a multi-modal extension of CCG. 1 Introduction Combinatory Categorial Grammar (CCG) (Steed- man, 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). It has been successfully used for a wide range of practical tasks, such as data-driven parsing (Hockenmaier and Steedman, 2002; Clark and Curran, 2007), wide-coverage semantic con- struction (Bos et al., 2004), and the modelling of syntactic priming (Reitter et al., 2006). It is well-known that CCG can generate lan- guages that are not context-free (which is neces- sary to capture natural languages), but can still be parsed in polynomial time. Specifically, Vijay- 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 anbncn. The generative capacity of CCG is com- monly attributed to its flexible composition rules, which allow it to model more complex word orders that context-free grammar can. The discussion of the (weak and strong) gener- ative capacity of CCG and TAG has recently been revived (Hockenmaier and Young, 2008; Koller and Kuhlmann, 2009). In particular, Koller and Kuhl- mann (2009) have shown that CCGs that are pure (i.e., they can only use generalized composition rules, and there is no way to restrict the instances of these rules that may be used) and first-order (i.e., all argument categories are atomic) can not generate anbncn. 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. A question then is whether the result carries over to pure CCG with higher-order categories. In this paper, we answer this question to the pos- itive: We show that the weak generative capacity of general pure CCG is still strictly smaller than that of the formalism considered by Vijay-Shanker and Weir (1994); …

Content truncated to 500 words