A Complete, Efficient Sentence-Realization Algorithm for Unification Grammar
A Complete, Efficient Sentence-Realization Algorithm for Unification Grammar
复制标题
一种完整、高效的统一语法句子实现算法
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Robert C. Moore
中科院分区：
文献类型：
--
作者：
Robert C. Moore
本文描述了一种有效的句子实现算法，该算法对于非常通用的统一语法类来说是完整的。在语法相当适度的约束下，该算法被证明具有多项式时间复杂度，可以生成其逻辑形式与目标逻辑形式完全匹配的句子。该算法可以扩展以处理可以说是逻辑形式等价问题最重要的子情况，即逻辑合取的排列。通过这种扩展，算法不再是多项式，但它似乎在问题性质允许的范围内尽可能高效。
This paper describes an efficient sentencerealization 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.