Dependency Trees and the Strong Generative Capacity of CCG

Alexander Koller and Marco Kuhlmann. Dependency Trees and the Strong Generative Capacity of CCG. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 460–468, Athens, Greece, 2009.

Abstract

We propose a novel algorithm for extracting dependencies from CCG derivations. 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: Although both formalisms generate the same string languages, their strong generative capacities are equivalent if we ignore word order, and incomparable if we take it into account.

Links