Dependency Trees and the Strong Generative Capacity of CCG

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 460–468, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Dependency trees and the strong generative capacity of CCG Alexander Koller Saarland University Saarbrücken, Germany koller@mmci.uni-saarland.de Marco Kuhlmann Uppsala University Uppsala, Sweden marco.kuhlmann@lingfil.uu.se Abstract We propose a novel algorithm for extract- ing dependencies from the derivations of a large fragment of CCG. Unlike earlier proposals, our dependency structures are always tree-shaped. We then use these de- pendency trees to compare the strong gen- erative capacities of CCG and TAG and obtain surprising results: Both formalisms generate the same languages of derivation trees – but the mechanisms they use to bring the words in these trees into a linear order are incomparable. 1 Introduction Combinatory Categorial Grammar (CCG; Steed- man (2001)) is an increasingly popular grammar formalism. Next to being theoretically well-mo- tivated due to its links to combinatory logic and categorial grammar, it is distinguished by the avail- ability of efficient open-source parsers (Clark and Curran, 2007), annotated corpora (Hockenmaier and Steedman, 2007; Hockenmaier, 2006), and mechanisms for wide-coverage semantic construc- tion (Bos et al., 2004). However, there are limits to our understanding of the formal properties of CCG and its relation to other grammar formalisms. In particular, while it is well-known that CCG belongs to a family of mildly context-sensitive formalisms that all gener- ate the same string languages (Vijay-Shanker and Weir, 1994), there are few results about the strong generative capacity of CCG. This makes it difficult to gauge the similarities and differences between CCG and other formalisms in how they model lin- guistic phenomena such as scrambling and relat- ive clauses (Hockenmaier and Young, 2008), and hampers the transfer of algorithms from one form- alism to another. In this paper, we propose a new method for deriv- ing a dependency tree from a CCG derivation tree for PF-CCG, a large fragment of CCG. We then explore the strong generative capacity of PF-CCG in terms of dependency trees. In particular, we cast new light on the relationship between CCG and other mildly context-sensitive formalisms such as Tree-Adjoining Grammar (TAG; Joshi and Schabes (1997)) and Linear Context-Free Rewrite Systems (LCFRS; Vijay-Shanker et al. (1987)). We show that if we only look at valencies and ignore word order, then the dependency trees induced by a PF- CCG grammar form a regular tree language, just as for TAG and LCFRS. To our knowledge, this is the first time that the regularity of CCG’s deriva- tional structures has been exposed. However, if we take the word order into account, then the classes of PF-CCG-induced and TAG-induced dependency trees are incomparable; in particular, CCG-induced dependency trees can be unboundedly non-project- ive in a way that TAG-induced dependency trees cannot. The fact that all our dependency structures are trees brings our approach in line with the emerging mainstream in dependency parsing (McDonald et al., 2005; Nivre et al., 2007) and TAG derivation trees. The price we pay …

Content truncated to 500 words