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.

Thu Nov 24 18:39:44 MET 1994