tailieunhanh - Báo cáo khoa học: "Dependency trees and the strong generative capacity of CCG"

We propose a novel algorithm for extracting dependencies from the derivations of a large fragment of CCG. Unlike earlier proposals, our dependency structures are always tree-shaped. We then use these dependency trees to compare the strong generative 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. | Dependency trees and the strong generative capacity of CCG Alexander Koller Saarland University Saarbrucken Germany koller@ Marco Kuhlmann Uppsala University Uppsala Sweden Abstract We propose a novel algorithm for extracting dependencies from the derivations of a large fragment of CCG. Unlike earlier proposals our dependency structures are always tree-shaped. We then use these dependency trees to compare the strong generative 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 Steedman 2001 is an increasingly popular grammar formalism. Next to being theoretically well-motivated due to its links to combinatory logic and categorial grammar it is distinguished by the availability of efficient open-source parsers Clark and Curran 2007 annotated corpora Hockenmaier and Steedman 2007 Hockenmaier 2006 and mechanisms for wide-coverage semantic construction 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 generate 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 linguistic phenomena such as scrambling and relative clauses Hockenmaier and Young 2008 and hampers the transfer of algorithms from one formalism to another. In this paper we propose a new method for deriving 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 .