Towards the Use of Automated Reasoning in Discourse Disambiguation.
In this paper, we claim that the disambiguation of referring expressions in discourse can be formulated in terms automated reasoners can address. Specifically, we show that consistency, informativity and minimality are criteria which (i) can be implemented using automated reasoning tools and (ii) can be used to disambiguate noun-noun compounds, metonymy and definite descriptions.
Introduction
It has long been thought that much of the burden of Natural Language
understanding and generation in automated systems could be carried
by inference. The most obvious early example of this is Winograd's
SHRDLU system (1973), implemented in PLANNER (Hewitt, 1969),
the earliest logic programming language. SHRDLU was a simulated,
language-understanding robot. It interpreted Natural Language input
in terms of decomposable procedures for achieving a state of the world
in which the input was true or for assessing whether it was already true,
with the resulting sub-goal structure (a plan or proof) then available
for answering questions about the system's actions. Thus SHRDLU
could understand and respond (either in language or simulated action)
to input utterances by proving that an utterance was meaningful, with
the proof providing a basis for its response.
While a full survey of inference in Natural Language understanding
is beyond the scope of this paper, besides SHRDLU it is worth mentioning
Charniak's PhD thesis (1972) on children's story understanding,
which assumes that stories are
\immediately translated into an internal representation which is
convenient for doing deduction" (Charniak, 1986), p.337.
Charniak's system used rules triggered by evidence in a story, to make
connections between story elements that are not expressed explicitly
and thereby to answer questions about the story.
In the 1980's, work on task-related dialogues by Allen and Perrault
(1982), Litman and Allen (1990) and others, showed how systematic
c
2001 Kluwer Academic Publishers. Printed in the Netherlands.
Claire Gardent and Bonnie Webber
inference on a hearer's part about a speaker's beliefs and goals could
be used in understanding questions (often fragmentary indirect speech
acts) and in responding to them cooperatively. Appelt's PhD thesis
(1985) was the most detailed study of its time of the role inference could
play in Natural Language generation, and the framework he developed
was able to produce utterances that could satisfy a hearer's domain
needs and his/her understanding abilities.
However, for a long time, formal reasoners were too slow and the
amount of knowledge they needed was too vast, to support their use in
anything other than a toy system or PhD thesis. This situation is now
changing: in Natural Language generation, fast automated reasoners
are being used in integrated systems for micro-planning (Stone, 1998;
Stone, 2000; Stone and Doran, 1997; Stone and Webber, 1998; Stone
et al., 2001; Gardent and Striegnitz, 2001), while in Natural Language
understanding { the concern of this paper { fast automated reasoners
are being employed over an ever-expanding range of problems.
In this paper, we focus on the role inference can play in disam-
biguation, provided that disambiguation problems can be formulated
in terms that automated reasoning tools can address. Here we look only
at reasoning in rst-order logic.
There are many types of ambiguities in natural language. Word
sense ambiguity arises from the fact that a word can have dierent
meanings. This has been addressed by e.g. (Charniak, 1986; Lehnert,
1986; Wilks, 1986) and (Hobbs et al., 1993) who showed how to identify
a word meaning in a given context using script-based and abductive
inference respectively. Structural ambiguity involves the possibility of
multiple syntactic analyses of a string. But since each syntactic analysis
may have a dierent semantic analysis, structural ambiguity often
correlates with semantic ambiguity as well, as for instance in prepositional
phrase and relative clause attachment (Crain and Steedman,
1985). Resolution ambiguity covers the many possible ways in which
semantically underspecied elements such as anaphors or ellipses can
be interpreted in a given context, while projection ambiguity refers to
the various ways in which a presupposition can be integrated into the
overall meaning of a text. The role that inference can play in resolving
projection ambiguity has been demonstrated by (Blackburn and Bos,
1999; Blackburn et al., 1999) who showed that existing rst-order theorem
provers and model builders can be used to weed out some of the
impossible readings. Scope ambiguity refers to the fact that a quantier
or a focus-sensitive operator such as \only" can include more or less
of its matrix utterance within its scope. Again (Blackburn and Bos,
have shown that rst-order automated reasoning tools can be
used to rule out some of the illegitimate scopings namely, those that
are incompatible with world knowledge. Finally, speech act ambiguity
refers to the alternative possible dialog functions that an utterance
can have. As mentioned earlier, plan-based inference techniques can
help deal with this problem (Allen and Perrault, 1982; Chu-Carroll
and Carberry, 1994; Litman and Allen, 1990; Lambert and Carberry,
1999), and statistical dialogue modelling may prove a help here as well
(Stolcke et al., 2000).
In this paper, we concentrate on how inference can be used to resolve
ambiguities involving referring expressions in discourse: specically, we
show that the method initiated in (Blackburn and Bos, 1999) for dealing
with projection ambiguity can be successfully used for resolving
underspecied entities and relations, by dispreferring resolutions that
lead to inconsistent or uninformative readings. Additionally, we argue
that model minimality is another factor that can be checked using automated
reasoning tools and can serve ambiguity resolution: given several
competing interpretations, these interpretations which are satised by
the smallest model (smallest domain, smallest interpretation function)
are often the preferred interpretations. The underlying intuition is that
minimal models yield interpretations that are more \coherent" than
non-minimal ones.
The paper is structured as follows. We start in Section 2 by arguing
for a certain type of interaction between NLP and automated reasoning
and show how checks for consistency, informativity and minimality can
be implemented using automated reasoning techniques. In Section 3, we
then consider the interpretation of noun-noun compounds, metonymy
and denite descriptions and show that their disambiguation through
contextual reasoning can be done through checks for consistency, informativity
and/or minimality. We conclude in Section 4 with pointers
for further research.
2. NLP and Automated Reasoning
There are essentially two ways to integrate automated reasoning into
NL understanding: one can use it to resolve underspecied interpretations
or one can use it to lter out unwanted interpretations resolved
by other means.
In the rst approach, which we will refer to as a constructive ap-
proach, an underspecied semantic representation i.e., a formula containing
rst-order and/or higher-order variables, has those variables
resolved (i.e., instantiated) in the course of being proven with respect to
the knowledge base. Thus a more specic representation is constructed
from one that is underspecied. This approach is used in (Hobbs et al.,
4 Claire Gardent and Bonnie Webber
1993; Gardent and Konrad, 2000a) and to a lesser degree in (Lascarides
and Asher, 1993). Thus (Hobbs et al., 1993) uses abduction to prove an
unresolved semantic interpretation. When this requires making assumptions
about the values of variables that make the formula true, these
assumptions become part of the interpretation, thereby specifying it
further. Similarly, (Lascarides and Asher, 1993) applies a process of
default inference to an underspecied discourse representation to compute
its semantic interpretation. Defeasible content added by default
also becomes part of the interpretation, again specifying it further.
As others have remarked, the use of abduction for NL understanding
has much in common with model-building, as in (Gardent and Konrad,
2000a; Baumgartner and Kuhn, 1999; Ramsay and Seville, 1999).
model builder is a program that takes a set of logical formulae  and
returns some of the models that satisfy .) Where model-building is
used for NL interpretation, the interpretation of a formula  is some
(carefully selected) model satisfying . As with abduction, a model may
make information explicit that is only implicit in the input formula
i.e. the semantic representation of the input discourse (Gardent and
Konrad, 2000a).
The merit of using reasoning to resolve underspecied interpretations
is that it integrates knowledge-based reasoning directly into the
interpretation process. In the case of model building, this has the advantage
of providing a consistency check \for free", since the only models
that will be built are both logically consistent and consistent with world
knowledge. If model building and/or abduction is used to produce a set
of possible interpretations for some input formula, members of the set
can be compared and ranked according to any desired metrics. This
provides a direct handle on the ranking of competing interpretations
for a given discourse.
The downside of using reasoning in this way is that ambiguity and
underspecication are resolved purely on the basis of semantic content.
This is in contrast with van der Sandt, who (in the case of presupposition
projection) makes essential use of the structure of the semantic
interpretation (van der Sandt, 1992). One can, of course, take this (and
anything else) into account, but it requires explicit encoding in terms
of additional predications. An approach that uses weighted abduction
to resolve interpretations also suers from the problem of motivating
the abductive cost of each type of assumption and verifying that it
produces the intended result whenever used.
The second way of integrating automated reasoning into NL understanding
is to use it to complement separate specialised algorithms for
resolving underspecication and ambiguity. In particular, when more
than one possible reading is found for the input discourse, automated
reasoning (in the form of theorem proving and/or model building)
can be used to lter out unwanted ones. For instance, (Blackburn
et al., 1999) compute all possible presupposition projections for an
input discourse using van der Sandt's projection algorithm (van der
Sandt, 1992), and then use rst-order theorem proving and model building
to apply van der Sandt's pragmatic constraints on presupposition
projection to eliminate implausible readings.
The drawback of such a ltering approach is that it requires all
ambiguities (including structural ambiguities, resolution ambiguities,
projection ambiguities, etc.) to be identied and the resulting possible
analyses enumerated. Dependencies between expressions and between
types of ambiguities can make the process of computing all and only
the possible analyses of a text, quite complex { a complexity that
the ltering methods presented here do not address. Moreover, a complete
enumeration seems far away from \how people process discourse",
although it does take advantage of what systems can do well
While a complete enumeration would be ine-cient if possible analyses
were simply ltered sequentially, ignoring commonalities that would
allow subsets to be ltered simulataneously, the input to ltering need
not be the entire set of possible interpretations of a (small) discourse. If
such interpretations could be generated in order of minimality (just as
in breadth-rst search, solutions are generated in shortest-rst order,
and in A* search, in best-rst order with respect to a given heuristic),
then consistency and informativity could be applied locally to either
accept the current interpretation, or reject it in favor of the one with
the next most minimal model that satises these tests. (This is what is
assumed in (Crain and Steedman, 1985).) Additional non-logical tests
(not described here) could then be applied to choose between readings
that were equally minimal or incomparable with respect to minimality.
In either case, we look to take advantage of the resources provided by
automated reasoners and tune them (through discourse-designed test
suites) to better satisfy our needs.
On the other hand, the value of a ltering approach is that it supports
a precise specication of what is relevant to each decision and
how it is used. For this reason, we adopt here a ltering approach,
starting with an enumeration of readings expressed in a many-sorted
rst-order logic. We then show that automated reasoning can use the
criteria of consistency, informativity and minimality to identify and
lter out unwanted readings. We shall see that in many cases, these
three criteria su-ce to eliminate linguistically invalid readings and rank
the remaining acceptable ones. First, however, we describe these criteria
and show how they can be tested using techniques from automated
reasoning.
6 Claire Gardent and Bonnie Webber
2.1. Consistency
It is well-known that rst-order consistency and validity problems are
undecidable: Given a formula , there is no guaranteed method of computing
whether or not  is consistent. However (Blackburn et al., 1999)
shows that state-of-the-art, sophisticated rst-order theorem provers
and model builders can be of practical use in checking consistency for
at least some classes of linguistic problems. The idea is to use theorem
provers and model builders in parallel.
Specically, suppose we want to check the consistency of . We can
simultaneously ask the theorem prover to prove : and the model
builder to construct a model that satises . If the theorem prover
succeeds, : is valid, hence  is inconsistent. (If the theorem prover
returns no result, either : is valid but the theorem prover ran of
resources, or : is invalid.) On the other hand, if the model builder
succeeds, then  is satisable and hence consistent. Although there
always remains the possibility either that both theorem prover and
model builder run out resources, or that neither program terminates
on some given input (even given unlimited resources), for at least the
presupposition projection problem studied in BBKN, state-of-the-art
automated reasoning systems return an answer almost all of the time
and do so reasonably e-ciently.
The question remains however, of whether the same will hold true
of all inference tasks in discourse understanding. We can only tell this
by clearly specifying the tasks. Developers can then try to tune their
systems to perform e-ciently and eectively on these tasks. The aim
of the present paper is to provide pointers to further language-related
tasks.
2.2. Informativity
BBKN show that informativity can be treated as a validity problem.
Suppose NEW is the formula we want to test for informativity. Then
it is informative with respect to a discourse context OLD and general
world knowledge KB just in case NEW is not entailed by OLD ^ KB.
Equivalently, NEW is informative with respect to OLD and KB just
in case (OLD NEW is not valid.
2.3. Minimality
Minimality, in some form, has continually been invoked as an important
factor in choosing among competing readings of a text, including (Crain
and Steedman, 1985; Johnson-Laird, 1983) inter alia. Intuitively, minimality
resembles the early AI planning heuristic (Sacerdoti, 1977): \Use
existing objects", but extended to include not just individuals but all
semantic entities e.g., properties, relations and propositions, and taking
\existing" to mean \discourse old" or \discourse salient". Minimality
thus serves discourse coherence by favouring readings which continue
to communicate about (or in terms of) the same things over those that
introduce new ones.
Although minimality is not as straightforward a concept as consistency
and informativity, nevertheless one can begin to identify the easy
cases and specify precisely how to capture various aspects of minimality
in a framework of automated reasoning { in particular, in a framework
of model building. Within such a framework, one can also begin to lay
down guidelines for constructing models in less straightforward cases,
to produce minimal models that accord with the speaker's intended
meaning.
As noted earlier, given a set of formulae , a model builder returns
some of the models satisfying . A model is a mathematical structure
that describes how the symbols of a logical theory are interpreted.
Specically, a model for a rst-order language L is a pair hI; Di with
D a non-empty set of entities (the domain of individuals) and I an
interpretation function which maps relation symbols in L to relations
of appropriate arity in D and constant symbols in L to elements of D.
Here we identify these models with sets of positive assumptions that
unambiguously dene the interpretation of the relation symbols and x
the interpretation of terms to rst-order entities that carry a unique
name. These are known in the literature as Herbrand models.
For example, given sentence (1a) and its logical form (1b), the
set (1c) is one of the Herbrand models satisfying (1b). In this model,
there is an individual c 1 who is a friend of Jon and who Jon interred
(i.e., buried).
(1) a. Jon interred his friend.
b.
The model M 1 denes an interpretation of the predicates friend and
inter over the universe of discourse g. It can also be taken
as a valid interpretation of (1a). There are, however, innitely many
other Herbrand models for (1b) which do not adequately capture the
meaning of (1a) e.g.,
The model M 2 declares Jon to be his own interrer, which is not the
intended or even a possible meaning of (1a) 1 . In the case of M 3 , the
1 The object of \inter" is, by denition, dead or at least taken to be so.
8 Claire Gardent and Bonnie Webber
model contains an extraneous assertion namely, that Jon is married. As
this is neither expressed nor entailed by the input discourse (1a), the
model fails to appropriately capture its meaning: while it is possible
to assume married(jon), it is not necessary for explaining the meaning
or truth of (1a). In short, just as in the story The Three Bears, while
some satisfying models are too small
some seem \just right" to capture the preferred meanings that a hearer
associates with a discourse. These are the ones we are interested in for
Natural Language applications.
To eliminate models that are \too big", we restrict the set of linguistically
interesting models to those models that are in some sense
minimal. The intuition is that the linguistically interesting models are
often those that show the truth of the input theory by making the fewest
possible assumptions and by using the fewest \objects" (i.e., individu-
als, properties, relations, propositions). In what follows, we make use of
a form of minimality introduced by (Gardent and Konrad, 2000a) for
interpreting denite descriptions namely, local minimality. Since this
notion incorporates both domain minimality and subset minimality,
we rst explain these two concepts.
Domain minimality (Hintikka, 1988; Lorenz, 1994) selects from among
the many models satisfying the input specication , those models that
have the smallest universe (i.e. domain of individuals).
Domain Minimality: Let  be a set of rst-order formulas and
S be the set of Herbrand models of . Then a model hI; Di 2 S is
domain minimal i there is no other model hI
the cardinality of D 0 is smaller than the cardinality of D i.e. jD 0 j < jDj.
By contrast, subset minimality (Bry and Torge, 1996; Schutz, 1999)
minimizes facts rather than individuals 2 .
Subset Minimality: Let  be a set of rst-order formulas and D
be the set of Herbrand models of . Then a model hI; Di 2 D is subset
minimal i there is no other model hI such that I 0  I.
Finally, local minimality requires models that satisfy some input
within a minimal domain D of individuals and are subset-minimal with
respect to all other domain minimal models. To spell this out explicitly:
be a set of rst-order formulas and D be
the set of Herbrand models of  that use some nite domain D whose
size is minimal. Then a model hI; Di 2 D is local minimal i there
is no other model hI such that I 0  I .
Subset minimality is also used in Circumscription (McCarthy, 1980), to dene a
consequence relation j=c such that j=c  i  is true in all subset-minimal models
of . In this paper, we do not use j=c , using subset minimality only as a way to help
determine a preferred interpretation.
Local minimal models are the simplest in the sense of Occam's Razor
and often the best explanation for the truth of an observation. By preferring
subset minimal models, for example, local minimality correctly
rules out M 3 as not yielding a correct interpretation of example (1a).
Eliminating models that are \too small" is less straightforward: the
problem is that a locally minimal model satisfying the input semantic
representation may not capture the preferred reading of the corresponding
discourse. In such cases, model theoretic semantics interacts
with other linguistic and non-linguistic knowledge sources (i.e., syntax,
prosody, pragmatics and world knowledge) to determine the preferred
reading, and it is this interaction that needs to be captured.
One simple instance of this interaction is illustrated by the discourse
(1a) and its locally minimal model M 2 , which does not adequately
capture its meaning. If the input specication were augmented with
appropriate world knowledge { namely, that one cannot inter oneself
{ then M 2 would never be constructed because the model builder can
only build models that are both logically consistent and consistent with
world knowledge. Thus M 1 would then be the locally minimal model
and hence the preferred reading for (1b).
More complex cases arise when factors other than world knowledge
contribute to ruling out locally minimal models that a hearer would
take to be \too small". For example, consider
a. Jon likes his friend.
b.
d.
Both M 1 and M 2 are satisfying models for (4b). But the locally mini-
mal, hence preferred, model for (4b) is M 2 which states that Jon likes
himself. Although this is a possible meaning for (4b) { i.e., if Jon's
only friend is himself { mutatis mutandis, M 2 is not the preferred
interpretation for (4a).
Here, pragmatics comes into play, as models such as M 2 can often
be eliminated by taking account of the Gricean maxim of manner: Be
perspicuous (Grice, 1975). Specically, if the speaker intended two NPs
to refer to the same object, she would have used a lexico-syntactic
construction that customarily implies this (i.e., Jon likes himself ).
So as long as appropriate knowledge from prosody, pragmatics, world
knowledge, etc. can be identied and included in the input specication
along with the semantic representation of the input discourse, model
building can automatically rule out any model that is inconsistent with
the overall input specication.
On the other hand, speakers often violate the Gricean maxims for
particular eects. For instance, in
Gardent and Bonnie Webber
(5) Jon admires his favorite person.
the speaker may intend for the hearer to recognise that Jon's favorite
person is Jon.
In short, minimality, even when combined with inconsistency, does
not produce a perfect test, ruling out all and only non-preferred read-
ings. But if we can characterise the situations in which it is a good test
(i.e., its false positive rate and false negative rate are low), it would be
worth applying in those cases.
Finally, note that minimality cannot, by itself, be used as a basis for
deciding between competing possible readings of anaphoric pronouns.
Consider
Jon insisted that Fred drive [but, because] he was too tired.
Models in which he co-refers with Jon and ones in which he co-refers
with Fred are equally minimal, but one seems preferred in the case
of \but" (i.e., Fred), while the other seems preferred in the case of
\because" (i.e., Jon). So the preferred interpretation must be decided
by other means.
The approximation of discourse coherence given us by local minimal
models is both less than and dierent from that used by (Lascarides
and Copestake, 1999; Asher and Lascarides, 1998) to resolve noun-noun
compounds, metonymy and denite descriptions. That treatment
is grounded in discourse coherence associated with discourse relations
(causality, narrative, background, concession etc.) that are taken to
hold between eventualities. Establishing what relation holds in a particular
case involves both logical deduction and defeasible reasoning.
In contrast, the minimality-coherence discussed here, while it does not
address the full discourse interpretation problem, involves only a simple
bias that can be checked using rst-order model building.
3. Case Studies
In the preceding section, we have proposed using automated reasoning
to lter out possible but unwanted (or non-preferred) readings of a
discourse, leaving either a single intended reading or a set of readings
among which a most preferred one can be chosen using non-logical
means (e.g., prior or conditional probabilities). We have suggested three
criteria that support this selection process { consistency, informativity
and minimality { and described how they can be assessed through automated
reasoning. Here we show how these three criteria can be used,
individually and jointly, in the discourse interpretation of three dierent
phenomena that are well-known for ambiguity: noun-noun compounds,
metonymy, and denite noun phrases.
In each case, we start with the set of possible semantic representations
of a text. Tests for consistency and informativity may then rule
some of them out. Local minimality is then applied to the set of locally
minimal models satisfying the remaining semantic representations. In
some cases, the set may contain models that do not stand in a subset
relation to each other, as when one model contains specic individuals
and another, generic ones. Such models are incomparable with respect
to local minimality. Where those models all embody legitimate and
equally preferred readings, ranking is neither required nor desired.
However, problems do arise where either incomparable models or
comparable models of equal minimality embody readings with dierent
degree of acceptability. In some cases, one may be able to appeal to
other types of minimality which draw on relations other than sub-
set. For instance, (Gardent and Konrad, 2000b) introduce conservative
minimality, a conservative extension of local minimality, to model the
interpretation of reciprocals. In other cases, factors other than minimality
will probably have to be brought into play to choose between
possible models, such as preferences for certain sources (e.g. world
knowledge versus discourse context) or types (e.g. anaphoric link versus
accommodation) of resolution, or notions of domain-specic salience or
likelihood. Our point is to show that e-cient automated reasoning can
quickly dispose of what is unwanted or non-preferred on formal grounds,
not that it solves the problem of discourse interpretation in its entirety.
3.1. Noun-Noun Compounds
Noun-noun compounds involve implicit relations between the denotations
of their component nouns. Because world knowledge admits so
many dierent relations { (Russell and Norvig, 1995) notes
Compound Relation
basketball shoes used-for
baby shoes used-by
alligator shoes made-of
designer shoes made-by
brake shoes part-of
(to which can be added \toe shoes" (used-for-standing-on) and \tap
shoes (containing), etc.) { noun-noun compounds have long held a fascination
for NLP research (Finin, 1980; Hobbs et al., 1993; Levi, 1979).
Recently, researchers such as (Lascarides and Copestake, 1999) have
begun to consider noun-noun compounds in the context of discourse
Gardent and Bonnie Webber
understanding, where new relations introduced by the discourse may
also be relevant to nding a referent for the noun phrase (NP) in which
the compound occurs. For example, in the isolated utterance
(7) The California student produced an excellent report.
the compound California student involves some relation between California
and student that can be attributed to the referent of the NP
\the California student". Here the most plausible relation holding between
a student (i.e., a person) x and a state y is known from world
knowledge to be x being from y. Thus, \the California student" most
plausibly refers to the student who is from California (whoever that is).
However, (Hobbs et al., 1993; Lascarides and Copestake, 1999) show
that in discourse, other relations are not only possible but preferred:
Each student was assigned a state to study. The California student
produced an excellent report.
While it is still possible that the intended relation between \student"
and \California" is that of being from, the most plausible relationship
between them that could be attributed to the intended referent of
the NP is student assigned to study California. This relation is one
made available by the discourse context, overriding possibilities made
available by general world or lexical knowledge.
In what follows, we assume that the possible interpretations of a
compound have already been identied by a separate process that has
access to the discourse context, lexical knowledge, and general world
knowledge. Checks for consistency, informativity and minimality can
then be used to determine which interpretation is preferred.
3.1.1. Minimality
Minimality can be used to determine the preferred interpretation of
Example (8), repeated below. 3
Each student was assigned a state to study. The California
student produced an excellent report.
As noted earlier, we assume that possible readings of each utterance
have already been identied { here, two dierent ways of resolving the
relationship between \student" and \California" { the rst (9a) arising
from the discourse context, and the second (9b), from the general world
knowledge:
a. The student assigned to study California produced an excellent
report
b. The student from California produced an excellent report.
3 In Example (7), the discourse context is empty, so the only relations available
for resolving the compounds are those provided by lexical and world knowledge.
To see how the preferred reading (9a) can be chosen on the basis of
minimality from among those oered for ltering, consider the following
models for Example (8).
Because M b1 and M b2 are both models for the same interpretation
of (8), M b2 would be eliminated from consideration by being less domain
minimal than M b1 , even though M b1 contains information not
entailed by reading (9b) { namely, that the student from California
who produced an excellent report was assigned to do that report on
California. Thus, as we saw before with Examples 1 and 4, minimality
sometimes delivers interpretations that are overly specic.
Applying local minimality to the remaining models M a and M b1 ,
the smallest model for (8) is M a . By taking the smallest (and hence,
the simplest) model explaining the truth of a discourse as yielding the
preferred reading { i.e., the one believed to be intended by the speaker
{ we can say that by minimality, (9a) is the preferred reading.
3.1.2. Consistency
Consider the following variant of (8):
After each student was assigned a state to study, the California
student, who had been assigned Ohio, started work immediately.
As with (8), there are at least two possible ways of resolving the relation
between \California" and \student". These lead to the following
meanings for the resolved discourse:
a. The student from California, who had been assigned to study
Ohio, started work immediately.
b. The student assigned to study California, who had been assigned
to study Ohio, started work immediately.
Assuming that a \quantity implicature" (Grice, 1975) leads us to
interpret \a state" in Example 11 as \exactly one state", reading (12b)
yields a contradiction. This is something that can be detected by a
consistency check, which would thereby rule it out. This leaves (12a)
as the preferred reading for (11).
Now consider another variant of Example 8:
Each student was assigned a state to study. The California student
agreed to work on Ohio.
14 Claire Gardent and Bonnie Webber
Again, there are two possible ways of resolving the relation between
\California" and \student", leading to the following further specica-
tions of the second sentence:
a. The student from California agreed to work on Ohio.
b. The student assigned to study California agreed to work on Ohio.
These interpretations are neither inconsistent nor uninformative. So
the same reasoning as in (8) would lead one to expect a preference
for (14b) by local minimality. Yet it is (14a) that seems preferred. One
possible and detectable explanation for this is that under interpretation
(14b), a presupposition triggered by the discourse becomes inconsistent.
Specically, if x agreed to P is taken to presuppose x was asked to P 4 ,
then the presuppositions of the two readings in (14) are:
a. The student from California was asked to work on Ohio.
b. The student assigned to study California was asked to work on
Ohio.
If \assigned to study California" entails \asked to work on California",
then presupposition (15b) is inconsistent. As (van der Sandt, 1992)
shows, inconsistent presuppositions result in discourses that are pragmatically
odd. 5 Assuming that consistency is applied to the presuppositions
of a discourse as well as to the discourse itself (using (Blackburn
et al., 1999) or perhaps the more e-cient approach described in (Monz,
1999)), (14a) will correctly be found to be the preferred reading for (13).
3.1.3. Informativity
Informativity can also be used to determine the preferred interpretation
of a noun-noun compound. Consider this next variant on Example 8:
Each student was assigned a state to study. The California student
was assigned California.
a. The student from California was assigned California.
b. The student assigned to study California was assigned California

Although interpretation (16b) has a smaller locally minimal model than
interpretation (16a), it is not preferred as it results in a non{informative
utterance.
As with consistency, however, informativity must also be applied to
the presuppositions of each interpretation, as in this nal variant of
Example 8:
4 This is because x didn't agree to P also seems to presuppose x was asked to P.
5 Presupposition (15b) is not inconsistent if one assumes dierent agents for
\assign" and \ask" (i.e., a dierent person assigning the student to study California
from the one asking her to work on Ohio). However, such a model would not be
constructed since it is not locally minimal.
Each student was assigned a state to study. The California student
agreed to work on California.
If the factive x agreed to P is taken to presuppose x was asked to P,
then the presuppositions of the two interpretations of (17) are:
a. The student from California was asked to work on California.
b. The student assigned to study California was asked to work on
California.
The non-informative presupposition in (18b) thereby makes its corresponding
reading dispreferred.
3.2. Metonymy
The second case we will look at involves metonymy { i.e., using a word
or phrase for another that it suggests { for example, using the container
for the thing contained or vice versa, as in
(19) The (wine, salt, meat) is on the table.
used for
(20) The (wine bottle, salt celler, platter of meat) is on the table.
Some verbs such as \start", \nish", \enjoy", \loathe", etc. that have
straightforward compositional readings when applied to events or activities
as in
nished preparing the peas.
are metonymic when applied to non-activities, as in
a. Jane nished the peas.
b. Sarah enjoyed California.
When the context is empty, as in (22), the preferred readings of
\nish the peas" and \enjoy California" are those given by lexical
knowledge i.e., nish preparing (or eating) the peas and enjoy visiting
California. Given an appropriate context however, as in
a. Jane was replenishing the shelves in the canned vegetable aisle.
After she nished the peas, she moved on to the artichokes.
b. Sarah read books about all the Western states. California she
enjoyed, but not the others.
the preferred readings are those that result in a minimal interpretation
i.e., replenish the shelves of canned peas and read about California.
We focus here on (23b), as \nish the peas" has a similar expla-
nation. To see how minimality yields the preferred reading for this
example, consider its models under the alternative reconstructions of
the metonymy. (For simplicity, we give the models for \Sarah read
about all the Western states. California she enjoyed." rather than for
the whole discourse):
Claire Gardent and Bonnie Webber
Compared with M b , M a has fewer assertions and is therefore locally
minimal. It also correctly re
ects the preferred interpretation for (23b),
the interpretation in which Sarah enjoyed reading about California
rather than visiting it.
minimality predicts that readings that \use existing objects"
are preferred over those that do not and therefore that interpreting
metonymy with respect to relations introduced by the previous discourse
will be preferred over interpreting it with respect to relations
made available by world knowledge.
In Section 2.3, we noted that minimality can make wrong predictions
in certain discourse situations and that it would be useful to be able to
avoid the expense of applying a local minimality lter there. Cases of
metonymy allow us to start identifying those situations. Consider the
following examples:
a. When Sarah read books about the American West, she really
enjoyed California.
b. After Sarah read books about the American West, she really
enjoyed California.
c. Before Sarah read books about the American West, she really
enjoyed California.
Example (25a) shows a preference for a discourse interpretation of
metonymy \reading about California", while (25b) shows a marked
dispreference, favoring the lexical interpretation { \visiting California".
(25c) is similar, although the eect seems less strong.
Since the only dierence in these examples is in the choice of con-
nective, this must be the source of the dierence in preferred readings.
What is known about \when" (Moens and Steedman, 1988) is that it
signals a causal or contingent relation between the eventuality described
in the \when" clause e when and that described in the matrix clause
e matrix . In explaining this, Moens and Steedman invoke the idea of an
event nucleus consisting of a preparatory process (prep(e)), followed by
an instantaneous culmination (cul(e)), and nally a consequent state
(conseq(e)). In these terms, a contingent relation holds between e when
and e matrix when e matrix is part of prep(e when ) (as in Example 25a) or
when it is part of conseq(e when ), as in
When Jon spilled wine over Harold, he apologised profusely.
On the other hand, \before" and \after" only convey a temporal relation
between the two eventualities. 6
Examples such as (25) therefore suggest that local minimality is
not an appropriate lter for discourse interpretations when temporally
distinct eventualities are being described. This does not mean that the
locally minimal interpretation may not, at times, be correct in such
situations { just that minimality ltering would be the wrong basis on
which to draw such a conclusion, since it will often lead to incorrect
results.
Notice that this predicts that one should also not use minimality
ltering in \when" clauses where e matrix is a separate eventuality that
is a contingent consequence of e when , as in
When Sarah read all the library's books about the American West,
she then really enjoyed California.
As predicted, minimality ltering gives an incorrect result.
The approach to metonymy presented here is complementary to
that presented in (Markert and Hahn, 1997; Hahn and Markert, 1999).
Markert and Hahn take the position that it is not type clashes that
signal to a reader that a phrase should be interpreted metonymically,
but rather a preference for interpreting denite noun phrases anaphorically
(i.e., as referring to a previously mentioned entity) or bridging
(i.e., as systematically related to such an entity). They address in
detail the complex reasoning involved in recovering relevant possible
interpretations of a metonymic phrase, as well as choosing the most
likely. Their self-imposed constraint of incrementality, however, requires
that they make this decision immediately before processing any further
material in the utterance. Thus their approach does not allow them to
take full advantage of tests provided by consistency, informativity and
minimality.
3.3. Definite Descriptions
In our nal case study, we show that minimality, consistency and informativity
can also be used in resolving denite descriptions.
Following (Strawson, 1950), singular denite descriptions (i.e. NPs of
the form the N ) are usually taken to presuppose the existence of some
6 Such a relationship does not by itself appear su-cient for coherent discourse,
and (25b) also implies positive causality (that the knowledge acquired through
reading enhanced the experience), while if anything (25c) implies negative causality
(that the knowledge acquired has now eliminated or diminished that enjoyment).
But causality is not an intrinsic feature of either \before" or \after", but rather
something deriving from the reader's beliefs about the eventualities themselves and
their possible relations.
Claire Gardent and Bonnie Webber
individual uniquely satisfying the given description. In what follows,
we will assume van der Sandt's anaphoric account of presuppositions
(van der Sandt, 1992) { that they are anaphors with an unusually rich
descriptive content. Like anaphors, presuppositions can be resolved to
some antecedent made available by the context. (Standard terminology
calls this cancelling). Unlike pronominal anaphors, however, it is
possible for a presupposition to \repair" the context by creating its
own antecedent, which is retrospectively added to the context in a
process called accommodation (Lewis, 1979). The following example
should clarify.
Suppose a story were to start o with one of the following:
a. The woman is single.
b. Terry loves Sally. The woman is single.
In (28a), the denite description the woman presupposes the existence
of a uniquely identiable woman. Since none is made available by the
null context, accommodation takes place and a woman is simply added
to the context. By contrast, in (28b) the woman can be resolved to Sally
(their referents are identied), and therefore no additional woman needs
to be accommodated.
The way a presupposition is resolved (whether and how it is resolved
or accommodated) is pragmatically constrained. In particular, the resulting
discourse must be both consistent and informative. For instance
in:
loves Sally. The woman is single.
the reading in which Mia is the single woman is ruled out by the
consistency constraint: a woman cannot simultaneously have a husband
and be single. Similarly, informativity can rule out readings that are
possible a priori. Thus in:
loves Sally. The woman is married.
although \the woman" could refer to Mia, this reading is dispreferred
as it would result in the uninformative discourse: Mia has a husband
and Mia is married.
The role of both informativity and consistency in constraining the
resolution possibilities of denite description presuppositions has been
discussed at length in (van der Sandt, 1992), and given a computational
treatment using automated inference systems in (Blackburn et al.,
1999; Monz, 1999). We will therefore concentrate here on cases where
minimality plays a decisive role in resolving denite descriptions.
As discussed at length in (Clark and Marshall, 1981), context can
make entities available for denite reference in several dierent ways,
including explicit mention (which (Clark and Marshall, 1981) call \lin-
guistic co-presence", and which we will refer to here as \anaphoric
linking") and associations grounded in world knowledge (which (Clark
and Marshall, 1981) call \indirect co-presence", which we will follow
common practice and refer to as \bridging").
As (Gardent and Konrad, 2000a) shows, local minimality nicely captures
the various ways in which a denite description can be resolved:
to some previously mentioned entity (31a, anaphoric linking), to some
associated entity (31b, bridging) or to some hearer-new entity (31c,
accommodation).
a. A woman sleeps. The woman dreams. (Anaphoric linking)
b. A car stopped. The engine had broken down. (Bridging)
c. The woman sleeps. (Accommodation)
The preference for anaphoric linking over other possibilities can be
attributed to the corresponding models having a smaller universe (do-
main minimality): the entity denoted by the denite description is the
same as that denoted by its antecedent. By contrast, both bridging
and accommodation require the denite description to denote an entity
that is distinct from all other entities explicitly introduced by the
previous discourse. The preference for bridging over accommodation
can be attributed to the corresponding models having fewer assertions
(subset minimality). For instance, with (31b), its bridging reading (32a)
is satised by model M a , whereas its accommodation reading (32b)
requires something like model M b . 7 Of the two models, M a is locally
minimal and therefore preferred.
stopped. The engine [of that car] had broken down.
b. A car stopped. The engine [unique but previously unmentioned]
broke down. (Accommodation)
broke down(c 3 )g
There are cases of bridging however, where the entity denoted by
the denite description is not itself entailed by the previous context.
For instance, in:
Jon entered the room. The chandelier was beautiful.
the rst sentence does not entail the existence of a chandelier. Neverthe-
less, \the chandelier" is interpreted as one hanging from the ceiling of
7 We assume the world knowledge that cars have engine, so that every model
\containing" a car also contains its engine.
Claire Gardent and Bonnie Webber
the room John entered. Again this preference for bridging is captured
by local minimality, as follows: if we assume that rooms have lights
and that chandeliers are lights, the following models could both be
constructed for
contains one more entity than M a , M a is locally minimal
and indicates the preferred reading.
So far we have looked at simple examples with minimal contextual
constraints. Constraints on the resolution of denite descriptions
can arise from more complex contexts however { in particular, from
relations between eventualities. Consider the following:
John rode into the oasis at 3pm. The camels were under the
palms, drinking water and resting.
John rode into the oasis at 3pm. The camels are now under the
palms, drinking water and resting.
Although a bridging reading for \the camels" is preferred in both
cases, the readings dier in what it is that \the camels" are associated
with. In (35), \the camels" must belong to the oasis, while in (36),
they could either belong to the oasis or have been John's means of
transportation for getting there. As in example (25), the dierence
between the two examples can be attributed to an interaction between
the temporal relationships between the eventualities and consistency.
Informally, the reasoning goes as follows.
In both cases, the rst clause denotes an event (e 1 ), and the second
a state (s 2 ). In (35), since both clauses are in the past tense,
we assume following (Kamp, 1979; Hinrichs, 1986), that s 2 overlaps
with e 1 . Because the eventuality e 1 denoted by the rst clause is an
accomplishment, we assume following (Moens and Steedman, 1988),
that it comprises a full event nucleus consisting of a preparatory process
prep(e 1 ), culmination point cul(e 1 ), and consequent state conseq(e 1 ).
Now e 1 (the arrival eventuality) involves a transition from John not
being at the oasis in prep(e 1 ) to John being there in conseq(e 1 ). Since
during the process of traveling, a person is collocated with their mode
of transportation, it follows that e 1 involves a transition from John's
means of transportation not being at the oasis during prep(e 1 ) to its
being there during conseq(e 1 ).
Turning to s 2 in (35), the claim in (Kamp, 1979; Hinrichs, 1986)
that it must overlap e 1 means that there are only three ways this can
happen: (1) s 2 starts during prep(e 1 ), or (2) it starts immediately at
hence one of the intrinsic consequences of e 1 , or (3) it
starts during conseq(e 1 ), with no commitment as to whether it is an
intrinsic consequence or not.
Here is where consistency and minimality interact with temporal
reasoning: In the case where s 2 overlaps with prep(e 1 ), identifying the
camels with John's means of transportation triggers an inconsistency,
since it requires temporally overlapping states to have contradictory
properties { John's camels not being at the oasis and John's camels
being there. Hence the camels cannot be taken to be John's means of
transportation and thus must be ones associated with the oasis. 8
In (36), on the other hand, the second clause is in the present tense,
so there is no assumption that its s 2 overlaps temporally with e 1 , there
is no such inconsistency. This allows \the camels" to be identied with
either the oasis or John's means of transportation. Because the models
are equally minimal by the arguments given so far, minimality can not
be used to choose between them. Still, it is clear that (36) shows a
preference for the \means of transportation" reading, and we leave for
future work whether rst-order automated reasoning systems can be of
help in nding it.
4. Conclusion
We have shown how one can come to the preferred discourse interpretation
of ambiguous sentences wholly or in part, by applying the criteria
of consistency, informativity and minimality to the possible interpretations
and their presuppositions. These were sentences with resolution
ambiguities associated with the linguistic phenomena of noun-noun
compounding, metonymy, and deniteness. As these criteria of con-
sistency, informativity and minimality can be assessed by rst-order
automated reasoning systems, we have in this way given further evidence
for BBKN's observation in (Blackburn et al., 1999) that rst-
order automated reasoning can play a role in automated discourse
understanding.
For this theoretical observation to be of practical interest however,
automated reasoners must perform e-ciently on the type of reasoning
tasks raised by the natural language data. Although Johan Bos's
DORIS (http://www.coli.uni-sb.de/~bos) system already provides an
Detecting inconsistencies based on temporal reasoning has not yet been addressed
by the current generation of model builders. This may be one of the gap
that test suites geared towards the problems of discourse understanding will cause
to be addressed.
22 Claire Gardent and Bonnie Webber
architecture in which to test this hypothesis, it only deals with a limited
set of data namely, projection ambiguity and resolution ambiguity. It
remains an open question how automated reasoners would scale to realistic
grammars, longer discourses and other types of natural language
related inference tasks such as those mentioned in the introduction.
When optimising automated reasoning systems for mathematics,
test suites of mathematics-related inference problems have allowed competing
approaches to be systematically trained and compared, pushing
them to become more sophisticated and e-cient at solving mathematics
related problems. Similarly, we believe that having test suites
for discourse understanding will allow the tuning of automated inference
systems to excel at strategies that support e-cient inference in
understanding Natural Language discourse.

Acknowledgements

We are grateful to Gann Bierner, Patrick Blackburn, Karsten Konrad,
Katja Markert, Natalia Nygren, Erik Schwarz and Mark Steedman for
helpful comments and discussion on material presented here. This work
was partially supported by the Project C2 (LISA) in SFB{378, grant by
the Deutsche Forschungsgemeinschaft to the University of Saarbrucken.



--R


Planning English Sentences.











Cambridge University Press



To appear in Journal of Language and Computation.









Mental Models: Towards a cognitive science of language





Morgan Kaufmann Publishers
th International Joint Conference on Arti
The Syntax and Semantics of Complex Nominals.







Computational Linguistics



Englewood Cli
A Structure for Plans and Behavior.







Submitted to Computational Linguistics.



Journal of Semantics

Morgan Kaufmann Publishers

Schank and K.

--TR

--CTR
Jochen L. Leidner , Gail Sinclair , Bonnie Webber, Grounding spatial named entities for information extraction and question answering, Proceedings of the HLT-NAACL workshop on Analysis of geographic references, p.31-38, May 31,
automated reasoning;discourse;semantics