Paper: Comparing Two Grammar-Based Generation Algorithms: A Case Study

ACL ID P92-1011
Title Comparing Two Grammar-Based Generation Algorithms: A Case Study
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1992
Authors

In this paper we compare two grammar-based gen- eration algorithms: the Semantic-Head-Driven Genera- tion Algorithm (SHDGA), and the Essential Arguments Algorithm (EAA). Both algorithms have successfully addressed several outstanding problems in grammar- based generation, including dealing with non-mono- tonic compositionality of representation, left-recursion, deadlock-prone rules, and nondeterminism. We con- centrate here on the comparison of selected properties: generality, efficiency, and determinism. We show that EAA's traversals of the analysis tree for a given lan- guage construct, include also the one taken on by SHDGA. We also demonstrate specific and common situations in which SHDGA will invariably run into serious inefficiency and nondeterminism, and which EAA will handle in an ...