Abstract
C, omi)utational ai)proaches to reference resolution, like Centering Theory, are best at resolving referring expressions which denote familiar reD.rents. We demonstrate how, by t~king a proof-theoretic approach to reference resolution within a Centering-type framework, we are able to make sense of reti;rring expressions tbr unfamiliar referents. These include, in addition to bridging descriptions, definite descripl;ions like "the first man" and "the first snowdrops of Spring". We claim that the first of these denotes a unique subset of a iflural discourse antecedent. While the second has no discourse antecedent, we similarly treat it as denoting a mfi(lue subset of a t'~nniliar referent.
Introduction
Itow do reti;rring exl)ressions denote? According to II.ussell, a definite description such as %he King of France", denotes a mfique individual by virtue of its meaning. But, according to Familiarity Theory (Helm, 1.983) , reti;rring expressions need not denote mfiquely by virtue of their meaning as they refer to individuals made familiar by the discourse or other context. This observation plays a key role in Centering Theory (Grosz and Sidner, 1986; Grosz et al., 1995) and other computational al)t)roaches in which rethrring expressions are resolved by locating their antecedents in the discourse. The reference of pronouns like "he", definite descriptions like "the woman", and referential tenses like "had" clearly has more to do with salience ill context thml with uniqueness of meaning. Similarly, while names like "Mary" need not denote individuals prominent in the discourse context, * \Ve would like to thank the anonymous reviewers for their detailed and helpful comments. they must nevertheless denote individuals familiar to conversants if they are successflflly to refer. However, there is another (:lass of referring expressions in relation to which we believe the concept of uniqueness of meaning does have an essential role to plt~y. These include such definite descrit)tions as "the first man" and "the first snowdrop of Spring", along with such variations on these as "the first three men" and "the first snowdrops of Spring".
Introduction
In implementing a system of retL, renee resolution, we have attemt)ted to reconcile the notions of familiarity mM uniqueness. This enables us to dereli;rence exl)ressions like "the first snowdrop of Spring" in a unified framework alongside anal)hers ~, pron(mns, retbrential tenses, names, and other definite descriptions like "the nlall".
Introduction
(1) Two men nrrive(t.
Introduction
(2) The .fir.st 'm,a'H, spoke. In the case of a referring expression like "the first mini", there may be an antecedent of sorts in the discourse, trot it is not the individual referred to (or indeed ml individual at all). We will say that the antecedent "two men" introduces a set, and that the referring expression "the first man" denotes, by virtue of the meaning of.first, a unique subset of this familiar set.
Introduction
(1) Mary saw th, e first snowd,vp of Spring.
Introduction
In the case of "tile first snowdrop of Spring", there need be no explicit antecedent in the discourse. We will s~w that, in the same way that "Mary" denotes a familiar individual, "the snowdrops of Spring" denotes a t'~nniliar set, or >vVe use this term to distinguish reflexives like "herself" from t)ronouns like "he" and "hiln".
Introduction
property. Again, by virtue of tile meaning of first, "tile first snowdrop of Spring" can be said to denote a unique subset of the familiar set. We will not claim that it denotes a unique individual, but that rather it denotes a unique subset of the specified cardinality, i.e., 1. This treatment has tile advantage that it extends to plural referring expressions.
Introduction
Below we outline the approach we have developed to the representation and resolution of referring expressions, betbre discussing in more detail its extension to deal with unfamiliar referents.
A Framework for Reference Resolution
Our framework for reference resolution has been implemented in the system of language understanding described in (Ramsay, 1999) . The starting point tbr reference resolution is the logical tbrm we obtain fl'om parsing. For example, the tbllowing is the logical tbrm we get for the utterance "Mary slept." 'e(,'e f ( aB ( V ech,_ti e( B , 1) )), A ) } 3C : {aspect(simple, A, C)} 0 (C, agen.t, ref (,kD (,,.amed(D, Mary) 
A Framework for Reference Resolution
We use tile inference engine described in (Ramsay and Seville, 2000) to update the discourse model with a new discourse state containing the intbrmation explicitly represented in tile logical tbrm together with any further inferences which are licensed given the existing discourse model. Reference resolution, which involves carrying out a proof that a retbrring expression denotes, is implemented as part of the update step. We anchor a referring expression
A Framework for Reference Resolution
tile discourse model by proving the existence of an entity in the model which satisfies the properties specified by the referring expression, in this case aD (na,~ed(D, Mary) 
A Framework for Reference Resolution
2Strictly speaking, it is a set which is denoted. For readability, our referring expressions conflate tim properties of sets and their members. In this case, the cardinality is a property of the set denoted, but the nmne Mary is a property of its member.
A Framework for Reference Resolution
Given that many referring expressions do not in themselves denote uniquely, however, we need a theory of reference resolution to enable us to obtain the appropriate (i.e., intended) reterent for any referring expression. We incorporate our theory of reference resolution into the actual representation of referring expressions; for example, we label anaphors with the property "salient" and pronouns (and also referential tenses) with the property "centred"3:
A Framework for Reference Resolution
Retbrence resolntion relies on maintaining, as in Centering Theory, a list of tbrward-looking centres for each discourse state (corresponding to an utterance) in the discourse. Furthermore, for the purposes of reference resolution, the discourse states themselves are organized into a discourse tree, which is constructed automatically based on referential cues 4, as described in (Seville, 1999) . The nodes in such a tree correspond to discourse states. Those oll tile right-hand frontier are open, which essentially means that tile entities mentioned in them are available to pronominal reference.
A Framework for Reference Resolution
The process of reference resolution for tile various referring expressions can be briefly described as tbllows. Anaphors, characterised as salient, are resolved to a less oblique argument of the same verb (Pollard and Sag, 1994) within the current discourse state, which is constructed aHere rcf (AD(cds(D) ) is a reference to the current discourse state and the properties m and f refer to male and female gender respectively.
A Framework for Reference Resolution
4The tree illustrated was constructed using pronominal cues. Each discourse state was attached as a daughter of the highest node in the discourse tree to which all pronouns and referential tenses (like had) mentioned in it could be anchored.
A Framework for Reference Resolution
incrementally. We also st;art our sere'oh tbr the referents of prononns and other centred entities in the current disconrse state, which is necessary if we are to resolw; such referring expressions as "her" in "Mary took John with her." However, referring expressions containing the property centred are prevented front 1)eing dereferenced to salient entities, thus ensuring that the constraint of disjoint reference is met.
A Framework for Reference Resolution
If we fail to tind the centred entity in the current discourse state, we search the previous open node and, if necessary, fllrther open nodes in the discourse tree, in order to deal with long-distance pronominalisation. The dereferencing of other referring expressions like ref (AD(named(D, Mary) gcard(D, 1))) is similar but less constrained in that we consider entities mentioned in all nodes mentioned in the discourse, tree, whether open or closed, in order of recency. This means that, essentially, names and definite descriptions are derefcreated to the most recently mentioned referent which is appropriate. Unlike in the case of pronouns, we also consider Discourse State 0, which doesn't correspond to an utterance but, rather, contains the background knowledge asstoned in the model. This is how we are able to deal with the first mention of a familiar referent like Mary (assmning that the properties kD (na, m(:d( D, Mary) gcard( D , 1)) sumce to distinguish a particular entity in Discourse, State 0 from all the others).
A Framework for Reference Resolution
Our approach extends naturally to cases like %he first snowdrop of Spring" because it; is proof-theoretic and so able to exploit background knowledge in reference resolution. This can be illustrated, in the first instance., by examthing the backgrmmd knowledge which is used in updating the utterance "Mary slept." The update step for this utterance yields Discourse State 1, contailfing (amongst others) the tbllowing facts: 
adult(#94)
These were generated from the lexical memfing 1)ostulates we stipulated for "Mary", "woman", and "folnale" :
adult(#94)
In this section we show how, within the framework above, we are able to make sense of a variety of referring expressions denoting unfamiliar referents. The most straighttbrward of these are bridging descriptions, so we start with these.
Bridging Descriptions
(1) Mary loves her" moth, or.
Bridging Descriptions
In this first case, "her mother", contains a referring expression nested within it;. Having dereferenced this, the knowledge that moth, er of is a fllnction enables us to obtain a unique reli;renl;. Our representation of the referring expression to be derelbrenced is as follows:
Bridging Descriptions
"her mother"
ref(AB(of(B,
,.e f ( a, 1)
ca .d( B, 1)))
Tile first step involves anchoring tile referring expression by dereferencing its nested rethrring expression for "her ''5.
ca .d( B, 1)))
'SThe referent for this is characterised as salient_or_centred as we allow I)ossessivc pronouns to be dereferenced as anal)hers or, failing that, as pronouns. 
Zove(#la6)
Tile partially constructed current discourse state we have when we do our dereferencing is as shown. "Mary" has already been dereferenced to #94 and this has been entered into the list of forward-looking centres fbr the current utterance. We are able to prove both salient(#94) and f(#94), and so our nested referring expression is dereibrenced to this entity.
Zove(#la6)
ref (kB(of(B, , F(,,,other( F) ), #94) card (m1)))
Zove(#la6)
It is then a straighttbrward matter to dereference the anchored referring expression, given the tbllowing facts in Discourse State 0:
card(#60(#94), 1)
These derive from our nmaning postulates fbr "mother ''6 and "of":
VXVYVZ(of(X, Y, Z) -+ Y.X)
Dealing with other bridging descrit)tions is more complicated:
VXVYVZ(of(X, Y, Z) -+ Y.X)
(1) Mary saw a house.
VXVYVZ(of(X, Y, Z) -+ Y.X)
(2) She tbund the door.
VXVYVZ(of(X, Y, Z) -+ Y.X)
In order to give an analogous treatment to the referring expression "the door", we have to treat it as elliptical tbr an exl)ression containing a nested referring expression, i.e., "the door of the house". In the same way that we have a meaning postulate for the relation mother of, we have one for the relation door of: aSkolemization preserves dm dependency of Y on X, i.e., #94 is present in #60(#94).
vx((ho,, e(x) v car(X)) qY (of (Y, AZ(door( Z) ), X)~eard(Y, 1)))
This means that, having used utterance (1 In updating utterance (2), the bridging description which needs to be dereDrenced has the tbllowing representation:
ref(AE(door(E) g~ card(E, 1)))
Since we caimot guarantee that there will only be a single entity in our model satisfying the
t)roperties kE(door(E) & card(E, 1)), we want
to ensure that the referent we obtain is either the most recently mentioned or that with the most recently mentioned antecedent, i.e., in this case, the house #139. Our ret>rence resolution t)rocedure exploits the fact that the house, #139, is explicitly represented in the forward looking centres of Discourse State 1 and that the intended referent, #46(#139), is clearly a flmction of this (its dependency having been preserved by Skolemization). In considering the potential refbrents for our referring expression ill order of recency, we attempt to prove, not simply, ibr each referent, X, whether door(X) and 
Superlatives
We are now in a I)osition to describe our treatment of the superlatives discussed in the introduction. First, we consider a case in which there is a discourse antecedent of sorts:
Superlatives
( .~(#108)
Superlatives
Our representation of the referring exi)ression "the first man" is as follows:
,.~f (~E(,,,o,,,,(~)))) x~ ,-..,.d(u. 1))))
The nested referring expression
ref(AE('m,a,'n.(E)))) ('m~ be straightforwardly
dereferenced in this case to give the anchored refi;rring exl)ression:
ref(AE('m,a,'n.(E)))) ('m~ be straightforwardly
rcf (A]3(mo,st(B, ac(,.~,,+.,j( c, .xu(,..,.~(J))))), #108) g ,..,,,,,.d(J3, ~)))) Dereferencing this then involves our meaning postulate fi)r superlatives:
VXVZVC(,-,,,,.d(Z, C)~(Z -X)~(~C = 1),~ V NV P (-wnosl.( X, P, _) -+ ~Y (mosl,(Y, P, X)&card(Y, N))))
This siml)ly says that tbr any severalton set X, any property 1 ) and any N, there is some set Y containing the N "most P" members of X. This meaning postulate does not translate into any facts in Discourse State 0, lint remains as a rule. When we have a particular referring expression to derefhrence, this rule enables us to prove that: ,x ( c ( ~,~,.ly( c, ~D ( .,,,,,.,( D ) ) ) ), #108) card(#81 (AA(c'arly (A,...)), 1, 2, @ 108, @ 108),
1)
In this way, we prove that the referring expression makes sense, i.e., denotes. However, unlike in the previous cases, we do not dereterence to a familiar referent. There are no existing facts in the database about the ref- (AA(early(A,...) ), 1, 2, @108, #108).
1)
Instead, in this case, we have to add to Discourse State 2 the facts we have proved.
1)
Discourse state 2 (AA(early(A,...) 
:~c(,,,a,~( c) ) )
, ,,,,,,,,(#81(~A(,,,,,,.ly(A, . . .) ), 1, 2, #108, #*O8)) mah '(#Sl(AA(early(A,...) ), 1, 2, #108, #108)) m(#Sl (AA(early(A,...) ), 1, 2, #108, #108)) ,,d,,,U,(#Sl(~A(~,,@(A,...)), 1, 2, #108, #108))
:~c(,,,a,~( c) ) )
The fln:ther facts we. prove, about our refe.rent being e~rly, male, etc., are required if we are to be aMe to subsequently retb.r to it using referring expressions such as "he". The.se are generated from a set of associated memfing postulates:
VXVYVP((ordered(P)~most(Y, P, X)) -+ P.Y) V A ( ordered( AB (early( B, A))))
vxvP (,.~o,,.1,,(x, 1,) 
VX ('m, an( X) (X is h, uman)~male(X)&adult(X)) vx(mde(x) -~ re(x))
In addition to these, we have two further meaning postulates for superlatives: The first of these, the uniqueness meaning postulate, states that if there are two subsets of of a set which share the same cardinality mid the same superlative property, such as first, then they must be regarded as identical 7. The second simply ensures that any mffamiliar ret5r-ent which we obtain via our meaning postulates can sensibly regarded as a proper subset of its antecedent; that is, it prevents us regarding "two men" as a potential antecedent of "the first men":
VX ('m, an( X) (X is h, uman)~male(X)&adult(X)) vx(mde(x) -~ re(x))
(1) Two meni arrived.
VX ('m, an( X) (X is h, uman)~male(X)&adult(X)) vx(mde(x) -~ re(x))
(2) The first men,f(i) spoke.
VX ('m, an( X) (X is h, uman)~male(X)&adult(X)) vx(mde(x) -~ re(x))
Our treatment of superlatives without discourse antecedents is similar to that above.
VX ('m, an( X) (X is h, uman)~male(X)&adult(X)) vx(mde(x) -~ re(x))
(1) Mary saw th, c first snow&vps of Spring.
VX ('m, an( X) (X is h, uman)~male(X)&adult(X)) vx(mde(x) -~ re(x))
There is just one major difference. AF(carly(F, : a(of(a, ,\It(snowdrop(It) ), re f ( ), I(named( I, @ri..o) g rd(Z, 1))))))), kL(named( L, Spring) &card(L, 1)))))))
r' I( E
ref(),J(of(J, ( s o.odrop( K) ), re f (
E, VO ) ) )
The representation we obtain for the referring expression "the first snowdrops of Spring" is shown above. Like that for "the first man", this contains a nested referring expression:
E, VO ) ) )
The difference is that, in this case, there is no discourse antecedent for the nested referring expression. This means that, in order to 7practicaUy, this meaning postulate seems to be redundant. Our meaning postulates generate for us only one such subset and it is impossible for another to be introduced through the discourse as "a first man" is ungrammatical.
E, VO ) ) )
anchor our referring expression by dereferencing the referring expression nested within it, we need to introduce a meaning postulate for the nested referent (and one for its nested referent,
E, VO ) ) )
&card(X, pl) )
E, VO ) ) )
These meaning postulates simply introduce into Discourse State 0 the fact that there are snowdrops of Spring, in the same way that the meaning postulate for "Mary" introduced the fact that there is a singleton set containing an individual so named.
E, VO ) ) )
Given the above facts in Discom'se State O, anchoring our referring expression is straighttbrward.
E, VO ) ) )
f ( E(. ost( E, 1F(early(F, C(of(a, Mt (.snowdrop( H) ), #98)))), #101)
* car'd(E, P0)))
From this point onwards, the proof that this referring expression denotes proeeeeds in the same way as in the previous example. Given the meaning postulates for superlatives, we are able to prove:
* car'd(E, P0)))
#101) card(#81(~A(ear'ly(A,...)),pl,pl, #101, #101),
pl)
Again, as in the example above, the facts we have proved concern an nut~miliar referent, and so have to 1)e added to the current discourse state. 
pl)
We have shown how, l)y taking a t)root:theoretie approach to reference resolution, we can extend a Centering-tyt)e framework to make sense of tel!erring expressions for a w~riety of unfamiliar referents. Having made sense of such referring ext)ressions, we add their referents to our discourse model. This is how we would normally deal with indefinites rather than definites. However, this al)t)roach makes t)erfect sense, given our treatment of su('h referring exl)ressions as denoting unfamiliar subsets of familiar referents (regarded as sets). We claim that we are able to use definite descriptions to refer to the referents in question, despite their unfamiliarity, SO long as we Call prove that, by virtue of their meaning, they denote uniqnely. Having imt)lemented our approach in a system of language understanding which already deals with a wide variety of referring expressions, we have demonstrated its practicality. It also has interesting theoretical implications, since it suggests a way in which pragmatic theories of reference resolution, like Familiarity Theory, and semantic theories, like Russell's, may be reconciled. However, it is fair to say that the success of the approach is not yet proven. This is because we have yet to show that we can deal with a set of related referring expressions within a single fi'amework. The following example illustrates the kinds of cases we have in mind:
pl)
(1) Three meni ate.
pl)
(2) Two menj slept. (3) The first meni died.
pl)
Here, "first" in "the first men" is clearly pertbrming a dit[erent, discourse-related flmction from that it plws in the cases we have been considering. We have yet to tackle such difficult cases but, since they seem to require reasoning about sets, we believe that our inference-based approach to reference resolution is a good place to start.

{'paper_id': '10543165', 'title': 'Making Sense Of Reference To The Unfamiliar', 's2_url': 'https://api.semanticscholar.org/CorpusID:10543165', 'source': 'S2ORC'}