Paper: A Dynamic Programming Approach to Document Length Constraints

ACL ID W08-1125
Title A Dynamic Programming Approach to Document Length Constraints
Venue International Conference on Natural Language Generation
Session Main Conference
Year 2008
Authors

Natural language generation (NLG) applica- tions must occasionally deliver rhetorically coherent output under length constraints. For example, certain types of documents must fit on a single webpage, on a cell phone screen, or into a fixed number of printed pages. To date, applications have achieved this goal by structuring their content as a rhetorical tree and using a greedy algorithm to pick the dis- course elements to include in the final docu- ment. Greedy algorithms are known to pick sub-optimal solutions. This paper presents an alternate approach based on dynamic pro- gramming. 1 Document Length Constraints A number of language engineering applications have addressed the issue of generating coherent documents under length constraints, including NLG applications, e....