Important Properties of the Algorithm

next up previous
Next: Extensions Up: A Semantic-Head-Driven Generation Algorithm Previous: An Example

Important Properties of the Algorithm

Several properties of the algorithm are exhibited by the preceding example example.

First, the order of processing is not left-to-right. The verb was generated before any of its complements. Because of this, the semantic information about the particle ``up'' was available, even though this information appears nowhere in the goal semantics. That is, the generator operated appropriately despite a semantically nonmonotonic grammar.

In addition, full information about the subject, including agreement information was available before it was generated. Thus the nondeterminism that is an artifact of left-to-right processing, and a source of inefficiency in the Earley generator, is eliminated. Indeed, the example here was completely deterministic; all rule choices were forced.

Finally, even though much of the processing is top-down, left-recursive rules (e.g., rule (3)) are still handled in a constrained manner by the algorithm.

For these reasons, we feel that the semantic-head-driven algorithm is a significant improvement over top-down methods and the previous bottom-up method based on Earley deduction.

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