homeresources & publications › efficient generation from packed input


Efficient generation from packed input


Kay (1996) introduces chart generation, a simple and relatively efficient algorithm for generating strings from an unambiguous meaning representation. This paper extends Kay's algorithm to efficiently generate strings from packed meaning representations which encode a large number of meanings in a small amount of data. This is useful when trying to efficiently translate all of the possible meanings of a source sentence into a target language, or when trying to present a user with alternate paraphrases that distinguish the different meanings of a sentence. The new algorithm will typically generate in polynomial time in the size of the packed input when the grammar is context-free, the number of dependencies per semantic variable is bounded, and the disjunctions are relatively independent.


Maxwell, J. T. Efficient generation from packed input. In Intelligent linguistic architectures, edited by M. Butt, M. Dalrymple and T. H. King. Stanford, CA: CSLI Publications; 2006; 19-34.