Generation as Dependency Parsing

Alexander Koller and Kristina Striegnitz

In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL), Philadelphia, 2002.

Natural-Language Generation from flat semantics is an NP-complete problem. This makes it necessary to develop algorithms that run with reasonable efficiency in practice despite the high worst-case complexity. We show how to convert TAG generation problems into dependency parsing problems, which is useful because the optimizations in recent dependency parsers based on constraint programming tackle exactly the combinatorics that make generation hard. Indeed, initial experiments display promising runtimes.

Download: Download

BibTeX Entry
@InProceedings{gen-dg,
	author = {Alexander Koller and Kristina Striegnitz},
	title = {Generation as Dependency Parsing},
	year = 2002,
	booktitle = {Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL)},
	address = {Philadelphia}
}

Back: Publications