A Complete, Efficient Sentence-Realization Algorithm for Unification Grammar

This paper describes an efficient sentence-realization algorithm that is complete for a very general class of unification grammars. Under fairly modest constraints on the grammar, the algorithm is shown to have polynomial time complexity for generation of sentences whose logical form exactly matches the goal logical form. The algorithm can be extended to handle what is arguably the most important subcase of the logical-form equivalence problem, permutation of logical conjunction. With this extension the algorithm is no longer polynomial, but it seems to be about as efficient as the nature of the problem permits.