...generation".

The notes written in square brackets have been added by the author.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...occurs:

This rule states that verb phrases are built using a subcategorization list as in  [Pollard and Sag1987] (see also [VanNoord1993]). Elements of the subcategorization list (bound to the feature SC) are selected one at the time by this binary verb phrase rule. The value of the SC feature is a list of signs. In this rule, the first element of the feature SC of the second daughter is equated with the first daughter of the rule. The remaining elements on the list, i.e., the tail of the list is percolated to the mother node. If a verb selects several arguments this rule can be applied iteratively. Furthermore, it is stated in this rule, that the semantics of the second daughter is identical with the semantics of the mother. The string representation of this rule expresses that the strings of the subcategorized elements of a verb are concatenated ``inside-out'' in reverse order.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...parsing.

In [VanNoord1993] a more detailed discussion of the problems of simple top-down generators can be found.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...sub-phrase.

Note that both points are not explicitly required in Pereira and Warren's original work. Hence, although Shieber's approach is a generalization of their work, in the sense that he also applies it for generation, it also could be seen as a specialization of the Earley deduction method set up in [Pereira and Warren1983]. Basically, this observation is the starting point of our new approach, which could be seen as real generalization of Pereira and Warren's work.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...phrase.

Note that because of this requirement Shieber's algorithm is coherent in the sense that the generation process will not augment an input semantic expression.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...element.

Although I am using here the term introduced by Shieber et al., one should better use the term semantic functor, since this element need not necessarily be identical with the ``syntactic head'' of a phrase. For example, modifiers are often analyzed as the semantic functor of the construction they modified, whereas the modified part of the construction is the syntactic head (see also [VanNoord1993]).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...rule:

This example is taken from [Shieber et al. 1989] where they discuss the problem in a footnote on page 10.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...necessary).

It would be possible to avoid this kind of processing overhead also for , using so-called memoization techniques (for technical aspects of memoization see e.g., [Norvig1992, Pereira and Shieber1987]). In fact, [VanNoord1993] discusses the use of memoization for semantic-head driven generators. Memoization can only be performed in combination with subsumption tests. However, as argued by Van Noord, ``Even though the overhead involved in the implementation of such memo-relations is still considerable, it turns out that for many grammars the head-driven generator is more efficient if implemented as a memo-relation 7#7 by a factor 4 for typical grammars.'' ([VanNoord1993], pages 93-94). It is interesting to note that the same author (when motivating his own approach) emphasized as a disadvantage of Shieber's Earley style generator that ``7#7 the necessary subsumption checks (for example to check whether a result already is present in the chart) lead to much processing overhead.'' ([VanNoord1993], page 80).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...restrictors

The reader not familiar with the notation of restriction should consult section 4.1.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...object.

In the beginning of their formalization, unification was the predominant constraint solving mechanism; hence they often referred to as unification-based grammars.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...50#50.

In the remainder of the thesis we will make use of the optimized goal reduction rule, and will use the expressions `goal reduction' and `optimized goal reduction' synonymously, unless otherwise specified.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...languages.

This means that our approach will also work for the whole set of constructions provided by Smolka or for other complex constraint languages (see, e.g., [Backofen and Smolka1993, A¨it-Kaci et al. 1994]).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...path.

Here, we are following the notation given in [VanNoord1993].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...expressions.

Without loss of generality we can assume that parsing and generation are performed by the same program P. In case we assume a specific parser or generator P would simply trigger these algorithms by means of a flag.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...relation

This is also the case if the two grammars are automatically compiled from one competence grammar, see,e.g., [Strzalkowski1989, Block1991].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...completion

Pereira and Warren call these phases instantiation and reduction, respectively. Note that the scanning operation, known from Earley's algorithm can be seen as a special completion step, namely the completion with an lexical entry, i.e., a unit clause representing a terminal element.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...lemma).

Although, [Pereira and Warren1983] abstract away from a specific selection function, they do not suggest how to parameterize the selection in a concrete implementation. Furthermore, they only consider parsing under the paradigm of deduction.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...size=-1>SC.

In [Samuelsson1994] an alternative approach is taken for deriving restrictors automatically by making use of anti-unification (also known as generalization). Anti-unification is the dual of unification - it constructs the least general term that subsumes two given terms. In the case of restriction it is also used for detecting cyclic constraints.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...instantiated.

Most recently, [Johnson1993] also presents a deduction mechanim which makes use of a dynamic selection function. The basic use of this selection function, however, is to support a coroutine-oriented selection between the body elements of a clause. Since, he only focused on natural language parsing, we do not consider this method in more detail.

One should also keep in mind, that [Pereira and Warren1983] already abstracted away from a specific selection function. For example, they already outlined the idea of a head-oriented selection function for parsing. This is important to say, because often their approach is viewed to be restricted only for a left-to-right scheduling.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...process.

To be more precise, the selection function returns the index of the selected element. As long as no misunderstandings are possible, we will use selected element and index of selected element in the same sense.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...as

Pereira and Warren also specify goal statements in such a way, eventually because of the same reason.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...procedure.

Otherwise, we have to store separately the feature structures of a resolved query, because a resolved (and hence reduced) query would just be the clause of the form

177#177

Note that using the ANS atom is only a technical matter and it should be interpreted as a ``special empty head of a clause.'' However, since we want to stress also important implementational aspects of our algorithm, we have decided to make our implementation as transparent as possible.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...encoding.

It would also be possible to define the inference rules more abstractly in terms of logical inference rules as for example done by [Shieber1988]. However, we are interested in algorithmic and data structure aspects, since this will be important for the next chapters to come. Hence, we prefer a more programming language oriented specification of the inference rules.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...list.

In our implementation, we distinguish between new and old answers by means of an additional slot attached to an item named IGNORE, which is set to true, if an answer is pushed to the Result list. Then, during further processing this item is ignored. In a sense, the item has become garbage and could also be removed from the state set, by a kind of garbage collector for items.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...S.

Clearly, this is the worst case. In our implementation, items are stored in hash tables indexed by the lemma's head's predicate name. However, this is only adavantageous if the grammar uses category specific rules (as in ). If only schematic rules are used (as it is the case for the grammar in Appendix A), then hashing in the described way would not help much, since all lemmas have the same predicate name.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...items.

However, if we actually inherit the backward pointer from the previous predicted active item, then we may allow, that the string or semantic expression of the predicted active item may be changed. Of course, only if this is done in a consistent manner, we will be able to use a reduced item, i.e., a passive item also for reducing the active item from which the passive item has been predicted.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...version:

We do not claim that this fragment is linguistically adequate. Its sole function is to illustrate the behaviour of the uniform indexing mechanism.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...size=-1>NO.

We assume that only the empty head rule has this feature, and that other empty rules do not.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...guaranteed.

A formal treatment of this property can be found in [Dymetman1994].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...environment.

In [Keene1989] and [Winston and Horn1989] good introductions to CLOS can be found. In [Neumann1993] we describe an CLOS-based framework for natural language system design. This approach has been used for the realization of the architectural platform of the systems DISCO and COSMA, cf. [Uszkoreit et al. 1994].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...generation.

Thus viewed, we ignore for the moment relevant aspects of generation, like morphological and speech generation, since the main point to discuss already falls out without explicit consideration of these aspects.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...component:

We are using an HPSG-like notation close to that of [Pollard and Sagto appear].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...SEM':

If the generator is part of an intelligent help system, the choice of this reading could have tremendous effects on the system itself.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...information

This and the following representations of the example are simplified in order to make clear the relevant aspects of the current discussion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...utterance:

This example is taken from Rubinoff Rubinoff:88 and is originally from a corpus of speech collected at the University of Pennsylvania.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...components.

In the authors term, the strategic component corresponds to the conceptual system and the tactical to the linguistic system.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...node

In section 5.5.8 we give some more details how the actual used normal generator might be embed into the monitoring strategy.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...[Neumann1991a].

The BiLD project is supported by the German Science Foundation in its Special Collaborative Research Program on Artificial Intelligence and Knowledge Based Systems SFB 314. The project location is the department of Computational Linguistics at the University of Saarland, and the principle investigator is Hans Uszkoreit.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...grammar:

We also give English literal and (hopefully) correct translations. It should be clear that the English translations need not necessarily be ambiguous or unambiguous in the same way.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...size=-1>P.

Using a globally set flag to trigger incremental monitoring can also be useful if the flag can be switched off in a kind of any-time mode. For example, if the overall system receives important time constraints and if it is possible to change the value of MONITOR? from true to false interactively, the remaining semantic expression would be generated without monitoring.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...element.

The notion SISTER can be defined on the basis of dominance as follows (see [Partee et al. 1990]): A node x dominates a node y if there is a connected sequence of branches in the tree extending from x to y. If x and y are distinct, x dominates y, and there is no distinct node between x and y, x immediately dominates y. A node is said to be the daughter of the node immediately dominating it, and distinct nodes immediately dominated by the same node are called sisters.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...approach

The application of EBL for natural language processing just described is closely related to the method of Derivational Analogy (DA), developed by Carbonell to investigate analogical reasoning in the context of problem solving [Carbonell1983]. The DA technique solves a new problem by making use of a solution derivation that was generated while solving a previous problem. Solving new problems is performed by modifying previously obtained derivations. Because the derivations are justified, DA can be seen as a type of justified analogical reasoning.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...tense.

Actually we can parameterize the method with respect to the information that should be generalized using a method similar to that of a restrictor. It has been shown that the amount of information generalized has a direct reflection on the space and time behaviour of the system.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...generation.

In our current implementation we have already built in this mechanism.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...repairing.

In [Finkler and Schauder1992] a more general discussion of the effects of incremental output on incremental generation can be found. In [Levelt1989] a detailed discussion of possible repairing strategies is given.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...176).

[Johnson-Laird1983] has also advocated Early's parsing algorithm as the most plausible cognitive one, but he has considered less empirical data ([Hemforth1993], page 176).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.