- ...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).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.