The problem of generating a well-formed natural-language expression from an encoding of its meaning possesses certain properties which distinguish it from the converse problem of recovering a meaning encoding from a given natural-language expression. In previous work , however, one of us attempted to characterize these differing properties in such a way that a single uniform architecture, appropriately parameterized, might be used for both natural-language processes. In particular, we developed an architecture inspired by the Earley deduction work of Pereira and Warren , but which generalized that work allowing for its use in both a parsing and generation mode, merely by setting the values of a small number of parameters.
As a method for generating natural-language expressions, the Earley deduction method is reasonably successful along certain dimensions. It is quite simple, general in its applicability to a range of unification-based and logic grammar formalisms, and uniform, in that it places only one restriction (discussed below) on the form of the linguistic analyses allowed by the grammars used in generation. In particular, generation from grammars with recursions whose well-foundedness relies on lexical information will terminate; top-down generation regimes such as those of Wedekind  or Dymetman and Isabelle  lack this property, discussed further in Section 3.1.
Unfortunately, the bottom-up, left-to-right processing regime of Earley generation-as it might be called-has its own inherent frailties. Efficiency considerations require that only grammars possessing a property of semantic monotonicity can be effectively used, and even for those grammars, processing can become overly nondeterministic.
The algorithm described in this paper is an attempt to resolve these problems in a satisfactory manner. Although we believe that this algorithm could be seen as an instance of a uniform architecture for parsing and generation-just as the extended Earley parser  and the bottom-up generator were instances of the generalized Earley deduction architecture-our efforts to date have been aimed foremost towards the development of the algorithm for generation alone, so that we will have little to say about its relation to parsing, leaving such questions for later research.