CS @ CU CS @ CU

Generation as Dependency Parsing

Alexander Koller and Kristina Striegnitz

Proceedings of the 40th 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 (204 K)

BibTex Entry

@InProceedings{KolStr02, 
   author = {Alexander Koller and Kristina Striegnitz}, 
   title  = {Generation as Dependency Parsing}, 
   year   = 2002, 
   booktitle = {Proceedings of the 40th ACL}, 
   address = {Philadelphia} 
} 

Back: Publications