---

Next: Acknowledgements Up: A Semantic-Head-Driven Generation Algorithm Previous: Postponing Lexical Choice

---

Further Research

Further enhancements to the algorithm are envisioned. First, any system making use of a tabular link predicate over complex nonterminals (like the chained_nodes predicate used by the generation algorithm, and including the link predicate used in the BUP parser [10]) is subject to a problem of spurious redundancy in processing if the elements in the link table are not mutually exclusive. For instance, a single chain rule might be considered applicable twice because of the nondeterminism of the call to chained_nodes. This general problem has to date received little attention and no satisfactory solution in the logic grammar literature.

More generally, the backtracking regimen of our implementation of the algorithm may lead to recomputation of results. Again, this is a general property of backtrack methods, and is not particular to our application. The use of dynamic programming techniques, a la chart parsing, would be an appropriate augmentation to the implementation of the algorithm. Happily, such an augmentation would serve to eliminate the redundancy caused by the linking relation as well.

Finally, in order to incorporate a general facility for auxiliary conditions in rules, some sort of delayed evaluation triggered by appropriate instantiation (e.g., wait declarations [12]) would be desirable. None of these changes, however, constitutes restructuring of the algorithm; rather they modify its realization in significant and important ways.

---

Gertjan van Noord
Thu Nov 24 18:39:44 MET 1994