Dependency trees and the strong generative capacity of CCG

Alexander Koller and Marco Kuhlmann

In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics (EACL), Athens, 2009.

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.

Download: Download

BibTeX Entry
@InProceedings{ccg-eacl-09,
	author = {Alexander Koller and Marco Kuhlmann},
	title = {Dependency trees and the strong generative capacity of {CCG}},
	booktitle = {Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics (EACL)},
	year = 2009,
	address = {Athens}
}

Back: Publications