Referential Chains and the Common Ground

Anton Benz

Humboldt Universität Berlin DFG–Project Dialogsemantik Prenzlauer Promenade 149–152, 13189 Berlin toni.benz@german.hu-berlin.de

DRAFT (07.12.00)

Abstract In this paper we provide a description for how the iterated specific use of an indefinite NP can lead to the establishment of referential chains across dialogues and dialogue participants. We describe how they introduce discourse referents, how they are related to the common ground, and how this common ground can be represented by the dialogue participants. Of central concern is the methodological part. We combine methods known from dynamic semantics/DRT on the one side, and theories for multi–agent systems on the other. The last part provides us with a natural, and non–ad hoc model for mutual information, and the interpretation of dialogue acts.

1 Introduction

This is an investigation into the pragmatics of chains in dialogue which are established through sequences of specific uses of indefinite descriptions by different speakers, which are linked to one another, and which are related to the same object.

(1) At 7:00 am in Berlin Pankow the 12 years old Melanie gets bitten by a Doberman.

a) Later, the news agency announces: “At 7:00 am in Berlin Pankow a 12 years old girl got bitten by a Doberman.”

b) Then the radio station sends the massage: “In Berlin Pankow a Doberman bit a 12 years old girl...”

c) Ann listens to the news, and, later, she says to Bob: “Today, a girl has been bitten by a Doberman.” Bob asks: “Do you know where the girl comes from?”

All the uses of a girl have the specific reading. They are connected to the previous uses, and are related to the same object, Melanie. This becomes clear, if we consider the meaning of the definite description the girl in Bob’s question. It refers uniquely to Melanie, although neither Bob nor Ann need to know that.

1.1 Referential Chains

We can assume that basically each use of an indefinite NP introduces a new discourse referent into the knowledge base of the hearer. We may use here a DRT-like mechanism (Kamp & Reyle, 1993; v. Eijck & Kamp, 1997) which describes the way a hearer interprets an assertion by the speaker. What is of special interest in the case of the described chains, is that they build a connection between different dialogues, and therefore between different dialogue participants.

(2) Two passenger, Anna and Debra, observe how a Doberman bites a young girl, Melanie. The next day Anna meets Bob and Chris. They sit together, and she tells them that yesterday she saw how a young girl was bitten by a Doberman. Some weeks later, Chris meets Debra, and they come to talk about dangerous dogs. Debra tells him: “Last week, I witnessed how such a dog bit a little girl.” Chris: “Oh, really! Anne told me that she too saw how a Doberman bit a girl.”

[figure: Anna; Bob; Debra; Chris; Melanie’s situation]

Here, we have two dialogues, one between Anna, Chris and Bob, the other between Debra and Chris. One and the same object, Melanie, is the source for a branching chain. For subsequent dialogues, it will be necessary for the involved persons to keep track with whom they share which referent.

The problems here are closely related to the phenomena handled in the theory on First Order Information Exchange developed by P. Dekker (Dekker, 1997).

He starts out with examples like

(3) A: Yesterday, a man ran into my office, who inquired after the secretary’s office.

B: Was he wearing a purple jogging suit?

A: If it was Arnold he was, and if it was somebody else he was not.

He observes that A’s answer sounds strange, even if we assume that there was more than one person coming into the office, one of them Arnold. Dekker claims here that

All natural language terms (definite and indefinite noun phrases alike), are assumed to relate to specific subjects in the information state of a speaker. Indefinite noun phrases which set up discourse referents in a felicitous way, must refer to specific subjects in the information state of the speaker, although they may provide no clue so as to which of his own subjects a speaker refers to. (Dekker & van Rooy, 1999)

Dekker and van Rooy developed this approach further to handle belief attributions. The meaning of a discourse like “Melanie is a 12 years old girl. Chris believes that some dog bit her.” can be described by a DRS like:

x, y, yx, yz
Melanie(x)

twelve-years-old-girl(x) Chris(y)

y : \begin{matrix}x, z \\ dog(z) \\ bit(z, x) \end{matrix}

x is the source of yx

This framework can be developed straight forward to be able to describe the building of chains across dialogues and dialogue participants. We will do this in a framework of Multi–Agent Systems, see (Fagin e.al., 1995). I.e. we will describe the dialogues and the updates of knowledge bases of the participants as games. This has the advantage that we can exploit standard techniques to define the information an agent has in a certain dialogue situation in a possible worlds framework. Thereby, we can work with the usual definition of mutual knowledge. Multi–agent systems allow for a representation of the environment, and effects of actions on this context. We will make referential chains part of the environment, and describe how specifically used indefinites establish such chains. The source–relation, which is a primitive relation in the theory of Dekker and van Rooy, is thereby defined through the rules of the dialogue games.

1.2 Definite Reference and the Common Ground

The relation between established chains and the use of definite descriptions is of special interest, because it forces us to investigate how discourse referents are connected to the common ground.

It has become usual to identify the common ground with what is mutually known by the dialogue participants. The relation between the referential use of definite descriptions and mutual knowledge has been extensively studied in (Clark & Marshall, 1981). A major point was to show that, indeed, mutual knowledge — or common knowledge — of a fact φ(x) is necessary to refer with the φ to a given object a. Mutual knowledge of a fact φ is identified with a conjunction of all sentences of the form:

X_{1} knows that X_{2} knows that X_{3} knows that ... that X_{n} knows that φ,

where the X_{n}’s are dialogue participants and n ranges over all natural numbers. For a visual situation use, it can be shown that the referential use of a definite description def x.φ(x) is successful if the object referred to is the only one for which it is common knowledge that it has the property φ, see (Benz, 1999). In this case, the participants know the objects they talk about. But in case of an anaphoric use this is no more the case.

The referent of a definite description is an object in the real source situation which is normally not known to the discourse participants. But the uniqueness condition connected with definiteness is not a condition on these real objects but on the common discourse referents and their properties. E.g. assume that in Example (2) two reporter, A and B, listen to the last dialogue between Debra and Chris. It is not possible to continue with:

(4) A to B: We can make an interview with the girl.

Although there is one, and only one girl (φ) in the situation talked about, it is not possible for B to interpret the definite defx.φ(x) as there are two common discourse referents u_{i} with φ(u_{i}).

That the anaphoric referential use of a definite is sensitive only to the common discourse referents can be seen in the following example.

(5) At 7:00 am Anna observes how a Doberman bites the young girl Melanie. Some minutes later the Doberman attacks also another young girl, Stefanie. This time, it is Debra who observes it.

a) Then Anna meets Bob and Chris and tells them that she has seen how a Doberman attacked a young girl.

b) The next day, Debra meets Bob, and she tells him that the dog attacked also another young girl.

c) Later, she meets also Chris and tells him the same.

d) Chris, who does not know that Bob knows already the whole story, meets Bob again and says to him: “The young girl was not the only one who was attacked by the dangerous Doberman.”

The use of the young girl by Chris is felicitous although both of them know that there have been two young girls who were attacked by the Doberman. Only one of them is available through a common referent. There arises the problem that the referential use of a definite description def x.φ(x) is felicitous although there is no real object a such that φ(a) is mutually known.

We split the presentation of our theory in two parts. In the first part we provide a more informal description including some examples. In the second part we add the mathematics.

Part I

The Description of the Theory

In this part we provide for an informal outline of our theory. First we will describe a dialogue fragment with observations and assertions where we can represent referential chains. This is done by using theories of multi–agent systems. Then we ask how to interpret definite descriptions. We thereby introduce the notion of a common DRS. Finally, we consider the representation problem. We define a new dialogue fragment where participants also maintain representations for the common DRSes.

2 A Dialogue Fragment with Referential Chains

2.1 The Basic Idea for the Representation of Dialogue Situations

The following picture shows (a part of) the situation of Example (5) after a) where Anna told Bob and Chris that a young girl was bitten by a Doberman.

[figure: u_{1}; Anna; girl(u_{1}); u_{1}; Debra; girl(u_{1}); Stefanie; Melanie; Bob; Chris; u_{1}; u_{1}; girl(u_{1}); girl(u_{1}); The girl’s; situation]

We represent this situation in a tuple of DRSes, one DRS for each dialogue participant, a first order model M for the situation talked about, and a relation → which tells us which discourse referent is chained to which other referent, or object.

\begin{matrix}M \\ Mel \\ Ste \end{matrix} \begin{matrix}→ \\ Mel → u_{1}^{An} \\ Ste → u_{1}^{De} \\ u_{1}^{An} → u_{1}^{Bo} \\ u_{1}^{An} → u_{1}^{Ch} \end{matrix}  Anna An ; u_{1} ; girl(u_{1}) Debra De ; u_{1} ; girl(u_{1}) \begin{matrix}Bob Bo \\ u_{1} \\ girl(u_{1}) \end{matrix} Chris Ch ; u_{1} ; girl(u_{1})

We will consider only DRSes of a very simple form, i.e. the set of conditions Con_{D} for a DRS D will contain only first order formulas. Hence, each DRS can be identified with the conjunction of all these formulas. The free variables are the discourse referents in U_{D}. We will allow only for dialogue where each referent is connected by a chain to exactly one object in the situation talked about. Hence, the chains define for each discourse participant a an assignment function f_{a} for the free variables of the first order formula associated to D_{a}. This allows us to define the truth of this formula in the usual way. We write (M, f_{a}) ⊧ D_{a}. As a first order formula we can identify the meaning of a DRS D with the set of all pairs (N , f) such that (1) N is a first order model for a possible described situation, (2) f is an assignment function for the referents in U_{D}, and (3) (N , f) ⊧ D. This allows us to compare our approach with the usual semantic interpretation, e.g. (Kamp & Reyle, 1993), or related dynamic interpretations, e.g. (Dekker, 2000).

We will see later that we have to include additional information in the local states of dialogue participants. We will assume that the participants remember in which dialogue acts they have been involved, and which objects they have observed. We need observations in order to be able to start with situations where no participant has any knowledge about the situation talked about. Hence, we have to add to the local states of participants two entries. One consisting in a sequence of dialogue acts, the other one in a function which maps some of the referents to observed objects.

2.2 The Representation as Multi–Agent System

We describe the relevant fragment of possible dialogues as special cases of Multi– Agent Systems. Here, we follow the theory developed in (Fagin e.al., 1995). Within this framework we are able to describe the building of chains across dialogues and dialogue participants. I.e. we will describe the dialogues and the updates of knowledge bases of the participants as games. This has the advantage that we can exploit standard techniques to define the information an agent has in a certain dialogue situation in a possible worlds framework, and we get the usual definition of mutual knowledge.

The multi–agent system consists of the following components

1. A set S of global states.

2. A set ACT of possible dialogue acts.

3. A function P which tells us which dialogue acts can be performed in which dialogue situations.

4. A transition operation τ : ACT × S ⟶ S which models the effect of the performance of a dialogue act in a certain situation.

5. A set of initial dialogue situations S_{0}.

Dialogues are then identified with the set G of all sequences

⟨s_{0}, act_{0}, …, act_{n−1}, s_{n}⟩

where s_{0} is an initial dialogue situation, and:

• act_{i} ∈ P (s_{i}), i.e. act_{i} is possible in s_{i}.

• s_{i+1} = τ(act_{i}, s_{i}).

We denote by S(G) the set of all global states which may arise as a possible dialogue situation, i.e. all situations which belong to a G ∈ G.

We describe a dialogue fragment with assertions and observations which allows the building of chains by the use of indefinite NPs.

1. We assume that basically each use of an indefinite NP introduces a new discourse referent into the knowledge base of the hearer.

2. We use here a DRT–like mechanism which describes the way a hearer interprets an assertion by the speaker.

3. In order to be able to start with empty DRSes for the participants, we include observations in the set of possible dialogue acts.

4. In addition we assume that each participant remembers the dialogue acts he has been involved in. This is necessary in order to have some information about the dialogue in the local states of the participants.

2.2.1 Global States

A global dialogue state consists of the local states of the participants DP = {1, …, m}, and the state of the environment. They are represented by tuples

⟨M, →, D_{1}, …, D_{m}⟩

M: A first order model which describes the situation talked about.

D_{a}: A simple DRS extended with information (1) about the dialogue acts where the participant a was involved, and (2) about the real objects he has observed.

→: A relation between objects and subjects, or subjects and subjects, where a subject is a pair ⟨a, u⟩ of a participant a and a discourse referent u.

We write u^{a} for ⟨a, u⟩. If a new discourse referent is introduced into a DRS, then → will connect this referent to it’s source. A DRS D_{a} will have the form:

Participant a U_{D_{a}} Con_{D_{a}}

Dialogue Acts where Participant a was involved Objects he has observed

The knowledge of a participant in a multi–agent system is defined as the set of all global states where his local state is the same as in the real one. Hence, if he should have knowledge about others, there must be entries in his local state which contain information about them. This is the reason to include the sequences of dialogue acts where a participant has been involved. As will become clear from the definition of these acts in the next subsection, a participant therefore knows the group of involved participants, and the direct source of the information.

2.2.2 The Possible Dialogue Acts

We allow for three actions an agent can perform:

• send(a, H, D, l),

• get(a, H, D),

• observe(H, D, l). send(a, H, D, l): Represents an assertion of speaker a with co–present ad-

dressees H. D is a DRS, which is the result of translating the speaker’s utterance into a DRS by standard techniques, e.g. (Kamp & Reyle, 1993). l is an injective function which relates the discourse referents in U_{D} to the subjects in D_{a}.

get(a, H, D): An action performed on the local states of the dialogue participants b ∈ H who are the addressees of an assertion with content D and speaker a.

observe(H, D, l): If performed by an agent a, it means that he is a member of a (co–present) group H which observes some fact represented by a DRS D. l is an injective function which relates the referents in U_{D} to real objects in the universe |M|.

These actions can be performed as parts of joined actions. They can be identified with sequences (act_{a})_{a∈DP}, where act_{a} is one of the three (local) actions defined before. There are two sorts of joined actions:

• act_{a} = observe(H, D, l) with fixed H, D, l for a ∈ H, and act_{a} = ⊥ for a ∉ H.

• act_{a} = send(b, D, H, l) for a = b, act_{a} = get(H, D, l) for a ∈ H, and act_{a} = ⊥ for a ∉ H ∪ {b}, D, H fixed.

2.2.3 When do we Allow to Perform a Joined Action?

We have to say which joined actions can be performed in a global state s. We assume that a joined observation is always possible, if the observed facts really hold. If the joined action represents an assertion with send(b, H, D, l), then it should be a possible action in s, iff D_{b}^{s} ⊴_{l} D. Where D ⊴_{l} D′ holds between DRSes D, D′, iff l is a function from U_{D′} to U_{D} such that for all condition φ ∈ Con_{D′} φ/_{s}l is an element of Con_{D} where φ/_{s}l denotes the formula, where the free variables in φ are replaced by their l–values. E.g. let D_{b}^{s} and D be as follows where D_{b}^{s} is on the left and D on the right side:

u_{1}, u_{2}, u_{3}, u_{4}
Dob(u_{1})
girl(u_{2})
bit(u_{1}, u_{2})
Dob(u_{3})
girl(u_{4})
bit(u_{3}, u_{4})

u_{1}, u_{2} ; Dob(u_{1}) ; girl(u_{2}) ; bit(u_{1}, u_{2})

Then b is licensed to make an utterance with content D where the referents u_{1} and u_{2} in U_{D} are related either to u_{1} and u_{2} or u_{3} and u_{4} in the left DRS.

The relation D_{b}^{s} ⊴_{l} D is essentially Dekker’s (Dekker, 1997) condition for the licensing of first order formulas. It says that a speaker can only make an assertion represented by a DRS D, iff he has own information about the objects referred to. This does not mean that he must be able to identify the objects related to the discourse referents in his DRS. In our context, this condition implies that the speaker can make only true assertions. This leads to the following two conditions: observe(H, D, l): Is always possible if (M, l) ⊧ D.

send(b, H, D, l): It should be a possible action in a global state s, iff D_{b}^{s} ⊴_{l} D.

A (local) act get(b, H, D) can occur only as part of a joined action together with one send(b, H, D, l) action. It will always be performed, iff a send–act is performed.

For global states s we denote by P (s) the set of joined actions which can be performed in this situation.

2.2.4 The Effects of Performing an Action

What are the effects of performing a joined action (act_{a})_{a∈DP}?

Acts with send(b, H, D, l) These joined acts change only the local states of b and the members of the group H.

• send(b, H, D, l) does not change the state of the speaker b except that he remembers that he has performed this action, i.e. we assume that D_{b} has a component Act_{D_{b}} such that for the new state D′_{b} we get Act_{D′_{b}} = Act_{D_{b}}^{∧}⟨send(b, H, D, l)⟩.

• The adjoined act get(b, H, D) should result in a merge of D_{a} and D for a ∈ H, and in an extension of Act_{D_{a}} to Act_{D_{a}}^{∧}⟨get(b, H, D)⟩.

There is some freedom in defining this merge. We may assume that it introduces for each referent in D a new referent into U_{D_{b}}, and adds the conditions of Con_{D} to Con_{D_{b}} where the old variables are replaced accordingly. → belongs to the environment, and an assertion of the form send(b, H, D, l) has the effect that new chains are added to →. They will connect the newly introduced subjects in the addressee’s DRSes with subjects in the speaker’s DRS.

Common Observations In order to be able to start in our examples with empty representations, we consider also acts of joined observations. If a is a member of a group H, then an observation observe(H, D, l) should have the effect that D is merged to his old information D_{a} in such a way that new discourse referents are introduced for objects which he has not jet observed. We assume that D_{a} has a fourth component Obs_{D_{a}} which is an injective function relating referents in U_{D_{a}} to objects in |M|, i.e. a remembers which objects he has observed.

2.3 An Example

The precise definitions will be provided in the second part of the paper where we present the mathematics of our approach. We don’t go into greater details here.

We reconsider Example (5). First Anna observes that a Doberman bites Melanie, and Debra observes that he bites Stefanie. Let D denote the DRS

u_{1}, u_{2} ; Dob(u_{1}) ; girl(u_{2}) ; bit(u_{1}, u_{2})

We assume that the content of all asserted sentences can be represented by D. The two actions

act_{1} = observe({An}, D, l_{1}), act_{2} = observe({De}, D, l_{2}),

with l_{1}(u_{1}) = Dob = l_{2}(u_{1}), l_{1}(u_{2}) = Mel, l_{2}(u_{2}) = Ste, result in the global state:

\begin{matrix}→ \\ Dob → u_{1}^{An} \\ Mel → u_{2}^{An} \\ Dob → u_{1}^{De} \\ Ste → u_{2}^{De} \end{matrix} An u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{1} l_{1}

De u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{2} l_{2}

\begin{matrix}Bo \\ ∅ \\ ∅ \\ ∅ \\ ∅ \end{matrix} \begin{matrix}Ch \\ ∅ \\ ∅ \\ ∅ \\ ∅ \end{matrix}

(a) Then Anna meets Bob and Chris and tells them that she has seen how a Doberman attacked a young girl.

We assume, she said to them: A Doberman bit a girl. We can represent this assertion by the actions

act_{3} = send(An, {Bo, Ch}, D, l_{3}), act_{4} = get(An, {Bo, Ch}, D),

with l_{3}(u_{1}) = u_{1}^{An}, l_{3}(u_{2}) = u_{2}^{An}. It results in the global state:

\begin{matrix}→ \\ Dob → u_{1}^{An} \\ Mel → u_{2}^{An} \\ Dob → u_{1}^{De} \\ Ste → u_{2}^{De} \\ u_{1}^{An} → u_{1}^{Bo} \\ u_{2}^{An} → u_{2}^{Bo} \\ u_{1}^{An} → u_{1}^{Ch} \\ u_{2}^{An} → u_{2}^{Ch} \end{matrix} An u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{1}

                    act^{3} l_{1}

De u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{2} l_{2}

Bo u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{4} ∅

Ch u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{4} ∅

(b) The next day, Debra meets Bob, and she tells him that the dog attacked also another young girl.

We again assume that she tells him: A Doberman bit a girl. We can represent this situation by the actions

act_{5} = send(De, {Bo}, D, l_{5}), act_{6} = get(De, {Bo}, D),

with l_{5}(u_{1}) = u_{1}^{De}, l_{5}(u_{2}) = u_{2}^{De}. It results in the global state:

\begin{matrix}→ \\ Dob → u_{1}^{An} \\ Mel → u_{2}^{An} \\ Dob → u_{1}^{De} \\ Ste → u_{2}^{De} \\ u_{1}^{An} → u_{1}^{Bo} \\ u_{2}^{An} → u_{2}^{Bo} \\ u_{1}^{An} → u_{1}^{Ch} \\ u_{2}^{An} → u_{2}^{Ch} \\ u_{1}^{De} → u_{3}^{Bo} \\ u_{2}^{De} → u_{4}^{Bo} \end{matrix} An u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{1}

                   act^{3} l_{1}

De u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{2}

                               act^{5} l_{2}

Bo
u_{1}, u_{2}, u_{3}, u_{4}
Dob(u_{1})
girl(u_{2})
bit(u_{1}, u_{2})
Dob(u_{3})
girl(u_{4})
bit(u_{3}, u_{4})

                                           act^{4}
                                           act^{6}

∅

Ch u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{4} ∅

(c) Later, Debra meets also Chris and tells him the same.

We can represent this situation by the actions

act_{7} = send(De, {Ch}, D, l_{7}), act_{8} = get(De, {Ch}, D),

with l_{7}(u_{1}) = u_{1}^{De}, l_{7}(u_{2}) = u_{2}^{De}. It results in the global state:

\begin{matrix}→ \\ Dob → u_{1}^{An} \\ Mel → u_{2}^{An} \\ Dob → u_{1}^{De} \\ Ste → u_{2}^{De} \\ u_{1}^{An} → u_{1}^{Bo} \\ u_{2}^{An} → u_{2}^{Bo} \\ u_{1}^{An} → u_{1}^{Ch} \\ u_{2}^{An} → u_{2}^{Ch} \\ u_{1}^{De} → u_{3}^{Bo} \\ u_{2}^{De} → u_{4}^{Bo} \\ u_{1}^{De} → u_{3}^{Ch} \\ u_{2}^{De} → u_{4}^{Ch} \end{matrix} An u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{1}

                  act^{3} l_{1}

De u_{1}, u_{2} Dob(u_{1})

girl(u_{2})

bit(u_{1}, u_{2}) act^{2}

                              act^{5}
                              act^{7} l_{2}

Bo
u_{1}, u_{2}, u_{3}, u_{4}
Dob(u_{1})
girl(u_{2})
bit(u_{1}, u_{2})
Dob(u_{3})
girl(u_{4})
bit(u_{3}, u_{4})

                                          act^{4}
                                          act^{6}

∅

Ch
u_{1}, u_{2}, u_{3}, u_{4}
Dob(u_{1})
girl(u_{2})
bit(u_{1}, u_{2})
Dob(u_{3})
girl(u_{4})
bit(u_{3}, u_{4})

                                                       act^{4}
                                                       act^{8}

∅

3 The Uniqueness Condition for Definite Descriptions

For multi–agent systems it is usual to identify the knowledge of an agent a in a situation s relative to S(G) with the set of all situation which are indiscernible from s. Two situations are indiscernible for an agent a, iff his local states are identical for both situations. This allows us to include the information of agents about the global state, and their information about others into our model. We either may use Kripke–structures, see (Fagin e.al., 1995), or develop our theory along the lines of (Gerbrandy & Groeneveld, 1997) as a possibility approach. Both descriptions provide us with (equivalent) representations CG_{w}(H) of the common ground for a possibility w and a group H. It is a set of accessible possible dialogue situations and contains all possibilities which are possible according to the knowledge of one participant, possible according to the knowledge a participant can have according to the knowledge of an other participants, etc.

Hence, the general apparatus for multi–agent system provides us with a natural representation of the mutual information of dialogue participants. But in view of our problem to explain the anaphoric referential use of a definite description we need a representation which provides us more directly with information about which subjects with which properties are common. For this reason we introduce the notion of a common DRS.

First, that a DRS is joined should mean that it can be embedded into all the DRSes representing the knowledge of the members of the group H in such a way that the images of one referent are all connected to each other via a common source. Then, a DRS is mutually joined if it is joined, everybody knows that it is joined, everybody knows that everybody knows that it is joined etc. By an iteration of a suitable condition we get an intuitive definition of a common DRS.

More specific, D is a joined DRS for a group H and state s ∈ S(G), iff there is a family of injective functions (l_{a})_{a∈H} such that for all a ∈ H D_{a}^{s} ⊴_{l_{a}} D, and ∀u ∈ U_{D} ∃x ∀a ∈ H x →_{r} l_{a}(u), where →_{r} denotes the reflexive closure of →. l_{a} embeds D into the local DRS D_{a} of participant a. This is done for all participants in the group H. That a discourse referent u in U_{D} is intuitively joined is modelled by the condition that for all participants a ∈ H l_{a}(u) is connected via →_{r} to the same subject. We need the reflexive closure →_{r} of → because one of the agents b in the group H may have been a speaker who introduced l_{a}(u) to the rest of them. In this case l_{b}(u) must be connected to itself. In order to restrict the possible size of a joined DRS we add the condition that for all u, u′ ∈ U_{D}, u ≠ u′, there is at least one a ∈ H such that l_{a}(u) ≠ l_{a}(u′).

In order to define what it means that a DRS D is mutually joined we must iterate the condition of joinedness in a suitable way. Hence, D must be a joined DRS relative to a family (l_{a})_{a∈H}. Then, every member b of H must know that D is joined. Hence, for all b ∈ H and for all v which are possible for b in w there exists a family (l_{a}^{v})_{a∈H} such that D is joined in v relative to (l_{a}^{v})_{a∈H}. In addition, we require that l_{b}^{v} = l_{b}^{w}, and that all the l_{a}^{v}(u) are chained to the ‘same’ subject as in w, i.e.:

• If all l_{a}^{w}(u) have been chained to l_{b}^{w}(u), then in v we should also find that all l_{a}^{v}(u) are chained to l_{b}^{v}(u).

• If all l_{a}^{w}(u) have been chained to a subject x ≠ l_{b}^{w}(u), then in v we should find that the l_{a}^{v}(u)s are again chained to an x ≠ l_{b}^{v}(u).

By the iteration of this condition we get the definition of a common DRS C_{w}(D, H) for a group H in a situation w (Def. 8.2).

We consider again Example (5). For the last global state described on page 11, which represents the situation after (c), we find that the following DRS D is a maximal common DRS for the group H_{1} = {An, Bo, Ch}.

u_{1}, u_{2} ; Dob(u_{1}) ; girl(u_{2}) ; bit(u_{1}, u_{2})

Anna told them in situation a) that A Doberman bit a girl. Hence, the resulting structure is a substructure of all subsequent global situations. Therefor, we see that D is a joined DRS. As embeddings we can use the identity functions, i.e. for all a ∈ H_{1} we set l_{a}(u_{i}) = u_{i}.

[figure: u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Anna; u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Bob; u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Chris]

Anna’s utterance of A Doberman bit a girl produced this structure, which is a substructure of all subsequent global states. It allows for the embedding depicted on the right side.

[figure: u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Anna; u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Bob; u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Chris; u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2})]

It is clear that they are embeddings, and we can check that for all a and i = 1, 2 l_{a}(u_{i}) is chained to the same subject, namely u_{i}^{An}. This makes clear why we needed the reflexive closure in our definition: it allows us to chain the referents of the speaker to it’s own referents.

[figure: u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Anna; u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Bob; u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Chris; u_{1}; u_{2}; Dob(u_{1}); girl(u_{2}); bit(u_{1}, u_{2}); ·; ·; ·; Anna] If we want to show that it is a mutual DRS, then we have to look at the local states of the participants and their knowledge about each other. Let us consider e.g. the local state of Bob. He remembers that he was involved in the joined act defined by act_{3} and act_{4}, as act_{4} = get(An, H_{1}, D) was concatenated to Act_{Bo}, a part of his local state. But the general constraints for our dialogue fragment imply that for any dialogue where act_{4} is part of Bobs local state act_{4} is also a part of the local states of all

other members of H_{1}, i.e. of Chris local state. Furthermore, the rules imply that all referents which have been introduced into Bobs local state by act_{4} are chained to referents in the speaker’s, i.e. Anna’s, local state. The same follows for Chris. Hence, it follows that Bob knows that D is a joined DRS. This reasoning applies in the same way for Chris, and in a similar way for Anna. Hence, all know that D is a joined DRS.

The definition of indiscernability implies that all situations that are possible according to the knowledge of an agent possess the same local state for him. Hence, it follows that for all these possible global states D is a joined DRS. Furthermore, it shows that the embedding functions can be chosen in the right way. An iteration of this sort of reasoning shows then that D is a common DRS.

Note, that D is also a common DRS for the groups {An, Bo}, {An, Ch}, and {Bo, Ch} but not for {De, Bo, Ch}. It is also a maximal common DRS for the group {An, Bo, Ch}. This follows only because we restricted the way how a DRS can be embedded. If we do not include the conditions that the l_{a}s must be injective and that for all u, u′ ∈ U_{D}, u ≠ u′ there is at least one a ∈ H such that l_{a}(u) ≠ l_{a}(u′), then any DRS which results as an iterated merge of D to itself, i.e. D ⊕ D or (D ⊕ D) ⊕ D etc., would have been a common DRS.

4 The Representation Problem

The last section provided us with a reasonable description of a common DRS. But how can the participants have access to this DRS? The most intuitive way seems to be that they keep track of the discourse referents which have been introduced to each group, and about the properties of those referents. I.e. a participant will not only update his own DRS, if he gets some new information, but he will also update a DRS representing the knowledge of the group which commonly got this information. This leads to an extension of the local states. We add for each participant a and for each group H ⊆ DP, where he is a member of this group, representing DRSes D_{a,H}. In the same way as in the last section we can describe the update operations connected to the possible local acts send(a, H, D, l), get(a, H, D) and observe(H, D, l) for global states with representations. Together with the function P, which specifies which actions are possible in a certain situation, this will lead to a new set of possible dialogues G^{+} for the same sequences of actions.

The following figure describes (part of) the local state of Bob in Example 5 after his talk with Debra (2). The first column represents his total knowledge about the biting situation, the second his protocol for what he heard in common with Anne and Chris, and the third for what he has in common with Debra.

Bo u_{1}, u_{2}, u_{3}, u_{4} Dob(u_{1}) girl(u_{2})

bit(u_{1}, u_{2})

Dob(u_{3}) girl(u_{4})

bit(u_{3}, u_{4})

{Bo, An, Ch} ; u_{1}, u_{2} ; Dob(u_{1}) ; girl(u_{2}) ; bit(u_{1}, u_{2}) {Bo, De} ; u_{1}, u_{2} ; Dob(u_{1}) ; girl(u_{2}) ; bit(u_{1}, u_{2})

This representation shows also that we need to represent how the discourse referents in the second and third column are connected to the referents in the first one. u_{1} and u_{2} in the first have been introduced by the same assertion as u_{1} and u_{2} in the second one, whereas u_{1} and u_{2} in the third one have been introduced together with u_{3} and u_{4}. Hence, in a full representation we have to add functions l_{i,H} : U_{D_{i,H}} ⟶ U_{D_{i,{i}}} to each column.

We can show in general that the DRSes D_{a,H}, which are internal representations of agent a for the referents and conditions which are common for the group H, are identical for all a, b ∈ H. If Bob meets Chris, then he can apply the uniqueness condition which is connected to the definite the girl to his DRS in the second column. He finds there u_{2} as the only referent which represents a girl. As Chris will have the same representation for the common DRS, they both will interpret the description as relating to a subject which is chained to Melanie. But if Bob meets Debra, his use of the girl will single out the referent u_{2} in the third column, which is chained to the girl Stephanie. The identity of the D_{a,H}’s explains why the group can co–ordinate their interpretation of referentially used definites. Furthermore, we can prove the following:

1. The set of common DRSes for a group H has maximal elements.

2. The maximal common DRSes for a group H are identical up to substitutions of variables.

3. The representing DRS for a group H is a maximal common DRS for this group.

This shows in which sense the DRSes D_{a,H} are representations of the common ground: They are maximal common DRSes.

Part II

The Mathematics of the Theory

In this part we provide the formal description of our theory. We develop it in four sections. First we introduce the basic definitions relating to DRSes. In the second and third section of this part we introduce the two dialogue fragments as multi–agent systems. The first one describes the dialogue fragment with referential chains where the local states of the participants contain information about observed objects and actions they have been involved in. We denote the resulting class of games by G. The second fragment has local states where the participants have explicit representations for the common information. Here, the set of resulting games is denoted by G^{+}.

The following structure underlies the presentation of both fragments:

Actions  Games  Global  Possibilities  Common
States  Grounds
A(G) ⟵  G  ⟶ S(G) ⟶  W(G)  ⟶ CG(G)

I.e., in both cases we define a set G of games which describe all possible dialogues in the fragment. In the terminology of (Fagin e.al., 1995) such a set is called a set of Runs and is denoted by R. But this terminology seems to be less well suited if we want to describe possible ways how a dialogue can develop. Every dialogue G ∈ G has the form

⟨s_{0}, act_{0}, …, act_{n−1}, s_{n}⟩ ,

where the s_{i}s denote global states, and the act_{i}s dialogue acts. A(G) will denote the set of possible sequences of actions, S(G) the set of possible global states which actually can occur in a dialogue of G. W(G) denotes the system where we include in the global states of participants additionally their knowledge about the global situation, and therefore, about each other. This will be done by use of the standard definitions for knowledge in multi–agent systems. This allows us to describe the common ground for each possibility as a special information state. The function from S(G) to W(G) will be bijective. The others are only surjective.

In the last section of this part we introduce common DRSes. They serve us as the central structure which allows us to relate the two defined dialogue fragments G and G^{+} to each other. There we will also provide the central theorems.

5 Basic Definitions

We provide the definitions relating to DRSes, i.e. the definitions of DRSes, embeddings of DRSes, sub–DRSes, merge of DRSes, and a relation between DRSes which we call Dekker’s support.

Let L be a language of predicate logic, and 𝔐 a class of models for L. We assume that L contains all the predicates the dialogue participants can use to talk about an outer situation.

If φ is a L–formula, then we denote by F V (φ) the free variables of φ, and by BV (φ) the bound variables. We assume that there are two disjoint sets of variables U := {u_{i} | i ∈ N} and V such that for all φ we have F V (φ) ⊂ U and BV (φ) ⊂ V.

For 𝔄 ∈ 𝔐 we denote by |𝔄| the universe of 𝔄. Let |𝔐| := ⋃_{𝔄∈𝔐} |𝔄|.

Definition 5.1 (DRS) A proper DRS D is a pair ⟨U_{D}, Con_{D}⟩ such that:

• U_{D} is a finite subset of U.

• Con_{D} = {φ_{1}, …, φ_{m}}, m ∈ N, is a finite set of L–formulas such that for all φ ∈ Con_{D} F V (φ) ⊆ U_{D}.

If

• U_{D} = {u_{1}, …, u_{n}} for some n ∈ N,

then we call the DRS D regular.

Let 𝔄 ∈ 𝔐. For an assignment function f : U_{D} ⟶ |𝔄| we define

(𝔄, f) ⊧ D iff (𝔄, f) ⊧ φ for all φ ∈ Con_{D}.

This allows us to define the meaning [D] of a DRS:

[D] := {(𝔄, f) | 𝔄 ∈ 𝔐, f : U_{D} ⟶ |𝔄|, (𝔄, f) ⊧ D}.

Hence, the DRSes in our fragment have a very simple form, especially, we don’t have subordination of DRSes, or modal contexts.

Definition 5.2 (Sub–DRS, Embeddings) Let D and D′ be proper DRS. Then let

D ⊆ D′ iff U_{D} ⊆ U_{D′} and Con_{D} ⊆ Con_{D′}.

For f : U_{D} ⟶ U we define f(D) by

U_{f(D)} := f[U_{D}],
Con_{f(D)} := Con_{D}/_{s}f,

where we define the substitution operation /_{s}f as follows:

• φ/_{s}f is the result of substituting all free variables u in φ which are in the domain of f by their values f(u).

• m/_{s}f := {m′/_{s}f | m′ ∈ m} for sets m.

We introduce two merge operations D_{1} ⊕ D_{2} and D_{1} ⊕_{b} D_{2}. The first operation introduces for each discourse referent in D_{2} a new referent into U_{D_{1}}. ⊕_{b} provides for the cases where some referents in D_{2} should be bound to referents in D_{1}.

Definition 5.3 (Merge of DRS) If D_{1} and D_{2} are two DRS whith U_{D_{i}} = {u_{1}, …, u_{n_{i}}}, and Con_{D_{i}} = {φ_{1}^{i}, …, φ_{m_{i}}^{i}}, then we define the deterministic merge D_{1} ⊕ D_{2} of D_{1} and D_{2} by

U_{D_{1}⊕D_{2}} := {u_{1}, …, u_{n_{1}+n_{2}}},
Con_{D_{1}⊕D_{2}} := Con_{D_{1}} ∪ {φ_{j}^{2}/_{s}f | 1 ≤ j ≤ m_{2}},

where f : U_{D_{2}} ⟶ U

f(u_{j}) := u_{n_{1}+j} for j = 1, …, n_{2}.

We denote the class of all proper DRS by DRS.

If b is a partial function from U_{D_{2}} into U_{D_{1}}, then we define the merge relative b, D_{1} ⊕_{b} D_{2}, in the following way: Let {v_{1}, …, v_{m}} be the (order preserving) enumeration of U_{D_{2}} \ dom b, then

U_{D_{1}⊕_{b}D_{2}} := {u_{1}, …, u_{n_{1}+m}},
Con_{D_{1}⊕_{b}D_{2}} := Con_{D_{1}} ∪ {φ_{j}^{2}/_{s}f | 1 ≤ j ≤ m_{2}},

where f : U_{D_{2}} ⟶ U

f(u_{j}) := \{ \begin{matrix}u_{n_{1}+i} for u_{j} = v_{i} \\ b(u_{j}) for u_{j} ∈ dom b \end{matrix} .

It follows that D ⊕_{b} D′ = D ⊕ D′ for dom b = ∅.

Definition 5.4 (Dekker’s Support) Let D and D′ be proper DRS. Let l be a function from U_{D′} to U_{D}. Then D supports D′ relative l iff l(D′) ⊆ D.

We follow (Dekker, 1997) and write D ⊴_{l} D′ if the relation holds. Originally the relation ⊴_{l} was defined between information aggregates, i.e. sets of world–assignment pairs. If we assume that the information aggregates are just meanings of DRSes, then Dekker’s original definition reads for functions l : U_{D′} ⟶ U_{D} as follows (Dekker, 1997, p.30):

[D] ⊴_{l} [D′] iff ∀(𝔄, f) ∈ [D] ∃(𝔄′, f′) ∈ [D′] 𝔄 = 𝔄′ & f′ = f ∘ l.

It is easy to see that D ⊴_{l} D′ ⇒ [D] ⊴_{l} [D′]. The other direction ⇐ does not hold in general because D ⊴_{l} D′ is a syntactic relation, whereas [D] ⊴_{l} [D′] is semantic. The distinction between DRSes is more fine-grained than that between information aggregates.

6 A Dialogue Fragment with Referential Chains

In this section we introduce the formal description of the fragment already discussed in Section 2. We will proceed in the following steps:

1. We define the set G of possible dialogues in our fragments as a set of games. We follow (Fagin e.al., 1995) and their definition of multi–agent systems. Hence we have to define

(a) The set of possible joined actions ACT.

(b) The set of possible global states S.

(c) The transition operation τ : ACT × S ⟶ S

(d) The Protocol P, which specifies which dialogue acts can be performed in which situation.

(e) A set S_{0} of initial dialogue states.

We first define a fragment where we allow only for assertions as dialogue acts. Then we add in a second step observations. We separated them because only assertions are in the focus of our interest, and observations are introduced just to be able to start with global states with empty representations.

2. Then we provide the definitions for:

(a) The set S(G) of global states which can actually occur in the fragment characterised by G.

(b) The set of possibilities W(G), where we represent the knowledge of participants about the dialogue situation, and about each other.

(c) The set CG(G) of common grounds.

We prove some very technical lemmas which we need later on, Lemma 6.7, 6.9 and 6.10.

Definition 6.1 (Dialogue Acts, Extended DRS) Let DP denote a finite set of possible discourse participants. For A, i ∈ DP we introduce the following sets of local acts:

ACT_{A}^{send} := {send(A, H, D, l) | A ∈ DP, A ∉ H ⊆ DP, D ∈ DRS, l :
U_{D} ⟶ U, l injective},

and

ACT_{B}^{get} := {get(A, H, D) | A ∈ DP, A ∉ H ⊆ DP, D ∈ DRS, B ∈ H}.

The set of all local acts for i ∈ DP is defined by ACT_{i} = ACT_{i}^{send} ∪ ACT_{i}^{get} ∪ {⊥}.

An extended DRS D is a triple ⟨U_{D}, Con_{D}, Act_{D}⟩ such that ⟨U, Con_{D}⟩is a proper DRS, and Act_{D} is a finite sequence of local acts for some participant i ∈ DP. Let DRS^{e} denote the set of all extended DRSes.

A joined act is a sequence (act_{i})_{i∈DP} such that there is an A ∈ DP, H ⊆ DP, D ∈ DRS, and l : U_{D} ⟶ U with

1. act_{A} = send(A, H, D, l), hence A ∉ H,

2. act_{i} = get(A, H, D) for i ∈ H,

3. act_{i} = ⊥ for i ∈ DP \ (H ∪ {A}).

We denote the set of joined acts by ACT.

Definition 6.2 (Global States and Chain Relation) For a fixed enumeration {A_{1}, …, A_{n}} of DP we denote by

S := {⟨𝔄, →, D_{A_{1}}, …, D_{A_{n}}⟩ | 𝔄 ∈ 𝔐, D_{A_{i}} ∈ DRS^{e}}

the set of global states. We abbreviate D_{A_{i}} by D_{i}, and for H ⊆ DP we identify H with {i ∈ N | A_{i} ∈ H}. → is a relation

→⊂ (DP × U) × (DP × U).

For ⟨⟨i, u⟩, ⟨j, v⟩⟩ ∈→, i, j ∈ DP, u, v ∈ U, we will write u^{i} → v^{j}.

Definition 6.3 (Transition Operation) We define a transition function τ : ACT × S ⟶ S: Let act = (act_{i})_{i∈DP} be a joined act and A ∈ DP with act_{A} = send(A, H, D, l). Let s = ⟨𝔄, →, D_{1}, …, D_{n}⟩ be a global state.

Then, we define τ(act, s) = ⟨𝔄′, D′_{1}, …, D′_{n}⟩ by

1. 𝔄 = 𝔄′

2. For i ∉ H and i ≠ A: D_{i} = D′_{i}.

3. For i ∈ H we set

• ⟨U_{D′_{i}}, Con_{D′_{i}}⟩ = ⟨U_{D_{i}}, Con_{D_{i}}⟩ ⊕ D,

• Act_{D′_{i}} = Act_{D_{i}}^{∧} ⟨act_{i}⟩.

4. For A we get

• ⟨U_{D′_{A}}, Con_{D′_{A}}⟩ = ⟨U_{D_{A}}, Con_{D_{A}}⟩,

• Act_{D′_{A}} = Act_{D_{A}}^{∧} ⟨act_{A}⟩.

5. For i ∈ H, U_{D_{i}} = {u_{1}, …, u_{n_{i}}}, and l(u_{k}) = u_{j} for u_{k} ∈ U_{D} and u_{j} ∈ U_{D_{A}} we have to add the following pairs to →_{s} in order to get →_{τ(act,s)}:

u_{j}^{A} → u_{n_{i}+k}^{i}.

We call the discourse referents in U_{D′_{i}} \ U_{D_{i}} introduced by act_{i}, and we write D′_{i} = act_{i}(D_{i}).

Definition 6.4 (Protocols and Dekker’s Condition)

Let s = ⟨𝔄, →, D_{1}, …, D_{n}⟩ be a global state. Then we define the protocol P by

P (s) = {(act_{i})_{i∈DP} ∈ ACT | act_{A} = send(A, H, D, l) ⇒ D_{A} ⊴_{l} D},

i.e. dialogue participant A is licensed to make an utterance with content D iff the information contained by D is supported by his own information D_{A} relative to l. We call this condition Dekker’s Condition.

Definition 6.5 (Observations) We extend the DRSes by a fourth component for the observed objects, i.e. we add a partial function Obs_{D} from U_{D} to |𝔐|. Then, we add a new set of local acts:

ACT_{i}^{observe} := {observe(H, D, l) | H ⊆ DP, i ∈ H, D ∈ DRS, l : U_{D} ⟶ |𝔐|}

and add to the set of joined acts ACT the set ACT^{observe} of all (act_{i})_{i∈DP} such that there are H, D and l with

• act_{i} = observe(H, D, l) iff i ∈ H,

• act_{i} = ⊥ iff i ∉ H.

For global states s = ⟨𝔄, →, D_{1}, …, D_{n}⟩ with chain relation, we add to the set P (s) the actions act = (act_{i})_{i∈DP} ∈ ACT^{observe} such that

act_{i} = observe(H, D, l) ⇒ (𝔄, l) ⊧ D

The transition operation τ is extended in the following way: τ(act, s) = s′ iff

1. 𝔄 = 𝔄′ and D_{i} = D′_{i} for i ∉ H.

2. For i ∈ H we have a partial function b_{i} with dom b_{i} ⊆ U_{D}, and

• u ∈ dom b_{i} iff ∃v ∈ U_{D_{i}} l(u) = Obs_{D_{i}}(v),

• b_{i}(u) = v ⇔ l(u) = Obs_{D_{i}}(v).

Then we can get

• ⟨U_{D′_{i}}, Con_{D′_{i}}⟩ = ⟨U_{D_{i}}, Con_{D_{i}}⟩ ⊕_{b_{i}} D,

• Act_{D′_{i}} = Act_{D_{i}}^{∧} ⟨act_{i}⟩.

3. For i ∈ H, U_{D_{i}} = {u_{1}, …, u_{n_{i}}}, and l(v_{k}) = a, where a ∈ |𝔄| and {v_{1}, …, v_{m}} is the (order preserving) enumeration of U_{D} \ dom b, we have to add the following pairs to →_{s} in order to get →_{s′}:

a → u_{n_{i}+k}^{i}.

The chain relation → is now a subset of

((DP × U) × (DP × U)) ∪ (|𝔐| × (DP × U)).

Finally, we have to define Obs_{D′}:

Obs_{D′_{i}} := Obs_{D_{i}} ∪ {⟨u_{n_{i}+k}^{i}, a⟩ | l(v_{k}) = a}.

We write again D′_{i} = act_{i}(D_{i}). Sometimes we will write v ∈ Obs_{D} instead of v ∈ domObs_{D}.

Definition 6.6 (Dialogue Game) A dialogue game is a sequence of the form G = ⟨s_{0}, act_{0}, s_{1}, act_{1}, …, s_{n}⟩, where the s_{j} are global states with chain relations, the act_{j} are joined acts, and where for all j < n

1. if s_{0} = ⟨𝔄, →, D_{1}, …, D_{n}⟩, then the D_{i}s are empty DRSes,

2. act_{i} ∈ P (s_{j}),

3. s_{j+1} = τ(act_{j}, s_{j}).

We will denote the final state s_{n} of G by G_{f} := ⟨𝔄_{G}, →_{G}, G_{i}, …, G_{n}⟩. We denote the set of all games by G.

The following lemma characterises the different ways in witch two subjects u^{i} and v^{j} can be connected to an object x by the chain relation.

Lemma 6.7 Let →_{r} denote the reflexive closure of the chain relation →. Let x →_{r} u^{i} and x →_{r} v^{j} for i ≠ j. Let G_{f} = ⟨𝔄, →, D_{1}, …, D_{n}⟩ be a global state for a dialogue G ∈ G. Then, one of the following cases holds:

1. u ∈ Obs_{D_{i}} and v ∈ Obs_{D_{j}} (⇒ x ∈ |𝔄|).

2. u ∉ Obs_{D_{i}} or v ∉ Obs_{D_{j}}.

(a) If u ∈ Obs_{D_{i}}, then u^{i} = x and v was introduced into D_{j} by an act act where act_{j} is of the form get(i, H, D) for some H ⊆ DP with j ∈ H, and some DRS D.

(b) If u ∉ Obs_{D_{i}} and v ∉ Obs_{D_{j}}, then either

i. x = u^{i} (⇒ x ≠ v^{j}), then v was introduced into D_{j} by an act act where act_{j} is of the form get(i, H, D) for some H ⊆ DP with j ∈ H, and some DRS D.

ii. x ≠ u^{i} and x ≠ v^{j}, then u and v were introduced into D_{i/j} by an act act where act_{i/j} is of the form get(A, H, D) for some H ⊆ DP with i, j ∈ H (⇒ A ≠ i, j), and some DRS D.

Proof: This lemma follows simply from the definition of the dialogues in G and the acts observe and send/get. □

Definition 6.8 (Global States for a Game G) Let G be given as in Definition 6.6. We denote by

S(G) := {s ∈ S | ∃G ∈ G G_{f} = s}

the set of all possible final states for G.

The following lemma collects some useful observations about the chain relation, discourse referents, and the way they have been introduced into the local DRSes by actions.

Lemma 6.9 Let s ∈ S(G), i ∈ DP. Let →_{r} denote the reflexive closure of →. Assume that s = G_{f} = s_{n} for some G = ⟨s_{0}, act_{1}, …, act_{n}, s_{n}⟩ ∈ G. Then

1. If u ∈ U_{G_{i}}, then there exists exactly one 1 ≤ m ≤ n such that u was introduced by act_{m}. Moreover, if u ∈ F V (φ), and act_{m} is not an observation, then all v ∈ F V (φ) and φ itself are introduced by the same act_{m}.

2. If u^{i} → v^{j}, and if u^{i} was introduced by act_{m_{1}} and v^{j} by act_{m_{2}}, then m_{1} < m_{2} and act_{m_{2}} is not an observation. It follows especially that → is irreflexive, i.e. u^{i} → v^{j} ⇒ v^{j} ↛ u^{i}.

3. x → u^{i} and y → u^{i} then x = y.

4. If x → u^{i}, and if u was introduced by act_{m}, where (act_{m})_{i} is of the form get(A, H, D), then x is of the form v^{A}.

Proof: We denote by lh(G) := n for G = ⟨s_{0}, act_{1}, …, act_{n}, s_{n}⟩ the length of G. Let s_{m} = ⟨𝔄, →^{m}, D_{i}^{m}⟩_{i∈DP}. We prove the lemma by induction over lh(G).

1. For lh(G) = 0 is nothing to show. Assume that lh(G) = n + 1. If u is introduced by act_{n+1}, then it can’t be an element of U_{D_{i}^{n}}. Hence, it is only introduced by act_{n+1}. For u not introduced by act_{n+1} it follows that u ∈ U_{D_{i}^{n}}, therefore, by I.H., it was introduced by exactly one act_{m}, m < n + 1. Let u ∈ F V (φ), and assume that u was introduced by an act_{m} which was not an observation. Hence, it follows by induction that u ∉ dom Obs_{D_{i}^{n+1}}. If φ would have been introduced by an observation, then F V (φ) would be a subset of the domain of Obs_{D_{i}^{n+1}} but this contradicts the assumption. Hence, φ was not introduced by an observation. Suppose it was introduced by an act_{m′} with m′ ≠ m. Then (act_{m′})_{i} is of the form get(A, H, D), i ≠ A. But then, all variables in F V (φ) have been introduced in this step, which again contradicts the assumption. This shows, that φ and all variables in F V (φ) are introduced with the same act as u.

2., 3. and 4. follow by induction over lh(G).

□

Lemma 6.10 Let s ∈ S(G), i ∈ DP. Let →_{r} denote the reflexive closure of →. Assume that s = G_{f} = s_{n} for some G = ⟨s_{0}, act_{1}, …, act_{n}, s_{n}⟩ ∈ G. Then

1. Let u^{A} →_{r} v_{k}^{i_{k}}, k ∈ {0, 1}, φ_{0} ∈ Con_{D_{i_{0}}} , v_{0} ∈ F V (φ_{0}). Suppose that v_{0}^{i_{0}} and v_{1}^{i_{1}} have been introduced by the same act_{m}, then there exist φ ∈ Con_{D_{A}}, φ_{1} ∈ Con_{D_{i_{1}}} and unique bijective f_{k} : F V (φ_{k}) ⟶ F V (φ) such that:

(a) ∀v ∈ F V (φ_{k}) f_{k}(v)^{A} →_{r} v_{k}^{i_{k}},

(b) φ = φ_{k}/_{s}f_{k},

(c) If g : F V (φ_{0}) ⟶ F V (φ_{1}), g(v) := v′ iff f_{0}(v) = f_{1}(v′), then φ_{1} = φ_{0}/_{s}g.

2. If a joined act contains a local act of the form get(A, D, H), then there exist for k ∈ {A} ∪ H unique injective functions l_{k} : U_{D} ⟶ U_{D_{k}} such that ∀k ∈ H ∀u ∈ U : l_{k}(u) was introduced by this joined act into D_{k} and l_{A}(u) → l_{k}(u). It holds l_{k}(D) ⊆ D_{k}.

3. Let act be a joined act which contains a local act act_{i} = get(A, D, H), i ∈ H. Let (l_{k})_{k∈H∪{A}} be given as in 2. Let D′ be a DRS, and let f_{i} : U_{D′} ⟶ U_{D_{i}} be injective with f_{i}(D′) ⊆ l_{i}(D). Then there exists a unique family (f_{k})_{k∈H∪{A}} such that for all k ∈ H ∪ {A} (1) f_{k} : U_{D′} ⟶ U_{D_{k}},

(2) f_{k}(D′) ⊆ l_{k}(D), and (3) ∀u ∈ U_{D′} l_{i}^{−1}(f_{i}(u)) = l_{k}^{−1}(f_{k}(u)). It follows that ∀u ∈ U_{D′} ∀k ∈ H f_{A}(u)^{A} → f_{k}(u)^{k}.

Proof: 1. As both, v_{0} and v_{1}, are introduced by the same act_{m}, it follows that A ≠ i_{k}, and that (act_{m})_{k} is of the form get(A, H, D) with i_{k} ∈ H, k = 0, 1, especially, act_{m} can’t be an observation. But then there is an φ′ ∈ Con_{D} such that v_{0} was introduced by a v ∈ F V (φ′) into U_{D_{i_{0}}^{m}}. (act_{m})_{A} must have been of the form send(A, H, D, l). It is clear that φ := φ′/_{s}l is the desired formula, and that we can get f_{k} from the definition of τ(act_{m}, s_{m−1}), and that the f_{k}s are unique. 2. is a consequence of 1. The family of function (f_{k})_{k∈H∪{A}} in 3. can be defined with the functions introduced in 1. and 2. □

There is a standard way to define the knowledge of an agent in a multi–agent system. Basically, this is done in a possible worlds framework, i.e. the beliefs of an agent are identified with a set of global states. This set is defined as the set of states which he can not distinguish from the actual one, i.e. where his local state is identical with his actual local state.

Definition 6.11 Let G be given as in Definition 6.6. We define an equivalence relation ∼_{i} for i ∈ DP on G × G

G ∼_{i} G′ iff G_{i} = G′_{i}.

G ∼_{i} G′ means that G and G′ are indistinguishable for agent i. G_{i} and G′_{i} denote here the local states of i in the final situations of G and G′, see Definition 6.6. We set

[D]_{i} := {G ∈ G | G_{i} = D}

For s ∈ S(G), s = ⟨𝔄, →, D_{1}, …, D_{n}⟩, we set

[s]_{i} := {s′ ∈ S(G) | ∃G ∈ [D_{i}]_{i} s′ = G_{f}}.

There are different ways to explicitly represent the knowledge of agents. One way is do define Kripke structures K = ⟨S(G), K_{1}, …, K_{n}⟩, where the K_{i}’s represent accessibility relations for the agents i = 1, …, n. Here, a global state s′ is accessible in state s for agent i iff the local states of i are indiscernible, i.e. iff s′ ∈ [s]_{i}. A specific dialogue situation can then be identified with the pair ⟨s, K⟩, or with s itself because K is fixed for G.

Another way to represent the information of agents in a multi–agent system is provided by the so–called possibility approach developed in the paper (Gerbrandy & Groeneveld, 1997). It directly adds the information states of agents to the global states. Both ways lead to equivalent representations^{1}. We don’t want to go into the technical details of the definition of possibilities. It is developed in a set theory with a special Anti–Foundation Axiom introduced by Peter Aczel (Aczel, 1988). In order to clearly separate the structures with and without explicit representation of knowledge we use the concept of possibilities in all subsequent sections. But it is always possible to read them as the related representations based on Kripke structures.

Definition 6.12 (Possibilities) For s ∈ S(G), s = ⟨𝔄, →, D_{1}, …, D_{n}⟩, and σ ⊆ S(G) we define

• I(s) = ⟨𝔄, →, ⟨D_{1}, I([s]_{1})⟩ , …, ⟨D_{n}, I([s]_{n})⟩⟩,

• I(σ) = {I(s) | s ∈ σ}.

We call I(s) a possibility, and I(σ) an information state. We denote the set of all possibilities for S(G) by

W(G) = {I(s) | s ∈ S(G)}.

We write I_{i}^{w} for the information states of agent i in a given possibility w ∈ W(G).

If one prefers Kripke structures, then I(s) is just ⟨s, K⟩, or s itself. I([s]_{i}) can be read as [s]_{i}.

Definition 6.13 (Common Ground) We get the common ground CG_{H}(w) for a group H of agents and a possibility w = ⟨𝔄, →, ⟨D_{1}, I_{1}⟩ , …, ⟨D_{n}, I_{n}⟩⟩ ∈ W as the smallest transitive superset of all I_{i} with i ∈ H, i.e. the smallest set σ with

• ∀i ∈ H I_{i}^{w} ⊆ σ,

• v ∈ σ ⇒ ∀i ∈ H I_{i}^{v} ⊆ σ.

We denote the set of all common grounds for G by CG(G).

For Kripke structures these definitions read as follows: A common ground for s and K is the smallest set σ closed under

• ∀i ∈ H [s]_{i} ⊆ σ,

• s′ ∈ σ ⇒ ∀i ∈ H [s′]_{i} ⊆ σ.

1See (Gerbrandy & Groeneveld, 1997), and especially (Gerbrandy, 1998, Prop. 3.7).

7 A Fragment with Representations for Common DRSes

In this section we introduce the dialogue fragment where the participants maintain explicit representations for the information and discourse referents they have in common with others. We describe it by a new set of games G^{+}. The underlying structure for the following definitions is the same as for Section 6. We don’t include the chain relation in the global states because we are only interested in the way how the participants maintain the explicit representations. But, of course, it would be no problem to do so.

Definition 7.1 Let S^{+} be the set of all ⟨𝔄, f_{1}, …, f_{n}⟩ such that

1. 𝔄 ∈ 𝔐,

2. fkt(f_{i}), dom f_{i} = {H ∈ P(DP) | i ∈ H},

3. f_{i}(H) = ⟨l_{i,H}, D_{i,H}⟩ with D_{i,H} ∈ DRS and D_{i,{i}} ⊴_{l_{i,H}} D_{i,H}.

Let ⟨𝔄, f_{1}, …, f_{n}⟩ ∈ S^{+} be given. U_{D_{i,H}} = {u_{1}, …, u_{n_{(H)}}}. For the local acts act_{i} ∈ ACT_{i} we define local updates. Let τ_{i}(act_{i}, f_{i})(H) := ⟨l′, D′⟩, i ∈ H ⊆ G, U_{D} = {u_{1}, …, u_{m}}, where ⟨l′, D′⟩ is given by the following conditions:

• act_{i} = observe(G, D, l) with i ∈ G and {v_{1}, …, v_{m}} the enumeration of {u ∈ U_{D} | l(u) ∉ ranObs_{D}}, then

1. D′ = act_{i}(D_{i,H}), see Definition 6.5, p. 21.

2. l′(u_{n+k}) := l(v_{k}) for 1 ≤ k ≤ m , and for 1 ≤ k ≤ n l′(u_{k}) = l_{i,H}(u_{k}).

• act_{i} = send(i, G, D, l) with i ∈ G, then

1. ⟨l′, D′⟩ = ⟨l_{i,H}, D_{i,H}⟩ for H = {i}.

2. D′ = D_{i,H} ⊕ D for H ≠ {i}

3. l′(u_{n+k}) := l(k) for 1 ≤ k ≤ m, and for 1 ≤ k ≤ n l′(u_{k}) = l_{i,H}(u_{k}).

• act_{i} = get(i, G, D) with i ∈ G, then

1. D′ = D_{i,H} ⊕ D,

2. l′(u_{n_{H}+k}) := u_{n_{{i}}+k} for 1 ≤ k ≤ m, and for 1 ≤ k ≤ n_{H} l′(u_{k}) = l_{i,H}(u_{k}).

Then, the global transition function τ for a joined act (act_{i})_{i∈DP} =: act is given by:

τ(act, ⟨𝔄, f_{1}, …, f_{n}⟩) := ⟨𝔄, τ_{1}(act_{1}, f_{1},), …, τ_{n}(act_{n}, f_{n})⟩ .

For s = ⟨𝔄, f_{1}, …, f_{n}⟩ we define the Protocol P by

P (s) := {(act_{i})_{i∈DP} ∈ ACT | act_{A} = send(A, G, D, l) ⇒ D_{A,{A}} ⊴_{l} D} ∪
{(act_{i})_{i∈DP} ∈ ACT | act_{i} = observe(G, D, l) ⇒ (𝔄, l) ⊧ D}.

The games in G^{+} should again start in situations where the participants have no entries in their representing DRSes. Hence, the class of initial dialogue situations S_{0}^{+} is the set of all ⟨𝔄, f_{1}, …, f_{n}⟩ ∈ S^{+} such that for all H ⊆ DP, 1 ≤ i ≤ n f_{i}(H) is empty. Therefore, we can identify the initial states for G and G^{+} and write S_{0} for S_{0}^{+}.

We can use the formulations of the definitions for dialogue games, Definition 6.6, global states for a game, Definition 6.8, possibilities, Definition 6.12, and the common ground, Definition 6.13 to define the related structures for S^{+}. For the definition of possibilities we set

[s]_{i} := {s′ ∈ S(G^{+}) | f_{i} = f′_{i}}.

The following theorem claims that all members of a group H maintain the same representations for the common DRS of this group. The proof is quite simple. We nevertheless call it a theorem due to it’s empirical importance. If this result would not hold, then it would be difficult to explain how the discourse participant can successfully coordinate their dialogue acts, especially the referential anaphoric use of definite descriptions.

Theorem 7.2 Let s = ⟨𝔄, f_{1}, …, f_{n}⟩ ∈ S(G^{+}), f_{i}(H) = ⟨l_{i,H}, D_{i,H}⟩. Then

∀H ⊆ DP ∀i, j ∈ H D_{i,H} = D_{j,H}

It follows by induction over the length lh(G) of games G ∈ G^{+}. This theorem allows us to write D_{H} for D_{i,H}, i ∈ H.

In the next section we will investigate the relation between the common ground in G and the common representations in G^{+}. The central concept will be that of a common DRS. For this investigation we need to compare games in G and G^{+}, hence we need to be able to relate them to one another. This is done by use of the sequences of actions which are part of the dialogues in G and G^{+}.

Definition 7.3 If G = ⟨s_{0}, act_{0}, …, s_{n+1}⟩ is an element of G or G^{+}, then we denote by a(G) = ⟨act_{0}, …, act_{n}⟩ the related sequence of actions.

Let A(G^{(+)}) be the set of all finite sequences of actions which can occur in G or G^{+}, i.e.

A(G^{(+)}) := {a(G) = ⟨act_{0}, …, act_{n}⟩ | n ∈ N, G ∈ G^{(+)}}.

By induction we can show that A(G) = A(G^{+}). Hence, we can write just A for A(G^{(+)}). This allows us to define for both games G and G^{+} and their initial states s ∈ S_{0} the sets

A(s) := {a(G) | G ∈ G^{(+)}, G = ⟨s_{0}, act_{0}, …, act_{n}, s_{n+1}⟩ & s_{0} = s}.

The following definition gives names to the maps in the following schema:

A ⟵^{a} G^{(+)} ⟶^{S} S(G^{(+)}) ⟶^{I} W(G^{(+)}) ⟶^{CG} CG(G^{(+)})

The function γ maps a possible sequence of actions for some initial state to the possibility correlated to it’s resulting final state.

Definition 7.4 • S : G^{(+)} ⟶ S(G^{(+)}), G ↦ G_{f}.

• I^{(+)} : S(G^{(+)}) ⟶ W(G^{(+)}), s ↦ I(s), see Def. 6.12.

• For a given initial situation s we can define a function which provides for each sequence of actions in A(s) the resulting final possibility: γ_{s}^{(+)} : A(s) ⟶ W(G^{(+)}), γ_{s}^{(+)}(a) = I(S(G(s, a))) where G(s, a) denotes the game in G^{(+)} which is uniquely determined by s and a. If s is given by context, then we write just γ^{(+)}.

• For H ⊆ DP and w ∈ W(G^{(+)}) let CG_{H}(w) denote the smallest set σ ⊆ W(G^{(+)}) such that for all i ∈ H I_{i}^{w} ⊆ σ, and such that ∀i ∈ H ∀v (v ∈ σ ⇒ I_{i}^{v} ⊆ σ).

The following lemma states that in both games, G and G^{+}, the participants build for the same sequence of dialogue acts the same DRSes which represent their total knowledge about the situation talked about.

Lemma 7.5 Let s ∈ S_{0}, a ∈ A(s), i ∈ DP. Then

D_{i}^{γ_{s}(a)} = D_{i,{i}}^{γ_{s}^{+}(a)}.

Proof: Follows by induction over the length of a. □

8 Common DRSes

We introduce the notion of a common DRS. The main result of this section, Theorem 8.11, shows that the explicit representations D_{H}^{γ_{s}^{+}(a)} for a possibility γ_{s}^{+}(a) in W(G^{+}) is in fact the maximal common DRS for a group H in γ_{s}(a) in W(G).

Definition 8.1 Let →_{r} denote the reflexive closure of a given chain relation →. Let w = ⟨𝔄, →, ⟨D_{1}, I_{1}⟩ , …, ⟨D_{m}, I_{m}⟩⟩ ∈ W(G). Let H ⊆ DP = {1, …, m}.

1. u^{i} ∼_{k} v^{j} iff ∃t ∈ U_{D_{k}} t^{k} →_{r} u^{i} & t^{k} →_{r} v^{j}.

2. u^{i} ∼_{0} v^{j} iff ∃t ∈ |𝔄| t →_{r} u^{i} & t →_{r} v^{j}.

3. u^{i} ∼_{x} v^{j} iff ∃k ≥ 0 u^{i} ∼_{k} v^{j}.

4. For D^{i} ⊆ D_{i} and D^{j} ⊆ D_{j} let D^{i} ∼_{ij} D^{j} iff

(a) ∃f : U_{D^{i}} ⟶ U_{D^{j}} ∀u ∈ dom f u^{i} ∼_{x} f(u)^{j} & f(D^{i}) ⊆ D^{j}, and

(b) ∃f : U_{D^{j}} ⟶ U_{D^{i}} ∀u ∈ dom f u^{j} ∼_{x} f(u)^{i} & f(D^{j}) ⊆ D^{i}.

u^{i} ∼_{k} v^{j} means that the subjects u^{i} and v^{j} are chained to the same subject in the local DRS of participant k. u^{i} ∼_{0} v^{j} means that they are chained to the same object in the described situation.

In the following definition E_{w}(l, D, H) means that the DRS D is a joined DRS for the group H in world w relative to l. We motivated this definition in Section 3. C_{w}(l, D, H) then means that D is common for H in w relative l, and the definition for E^{n+1} contains the conditions for the iteration of joinedness. E plays a similar role as the modal operator E for everybody in the usual definitions of common knowledge, see (Fagin e.al., 1995).

Definition 8.2 (Common DRS) Let D be a DRS and w = ⟨𝔄, →, ⟨D_{1}, I_{1}⟩ , …, ⟨D_{m}, I_{m}⟩⟩ ∈ W(G). Let H ⊆ DP, DP = {1, …, m}. Then

1. E_{w}(l, D, H) iff

(a) l = l^{(w)} := (l_{i}^{w})_{i∈H} is a family of functions l_{i} : U_{D} ⟶ U_{D_{i}},

(b) D_{i} ⊴_{l_{i}} D,

(c) ∀u_{1}, u_{2} ∈ U_{D} : u_{1} ≠ u_{2} ⇒ ∃i ∈ H : l_{i}(u_{1}) ≠ l_{i}(u_{2}),

(d) ∀i, j ∈ H l_{i}(D) ∼_{ij} l_{j}(D).

2. E_{w}^{1}(l, D, H) iff E_{w}(l, D, H),

3. E_{w}^{n+1}(l, D, H) iff E_{w}(l, D, H) & ∀i ∈ H ∀v ∈ I_{i} ∃l^{v} = (l_{j}^{v})_{j∈H}:

(a) l_{i}^{w} = l_{i}^{v}

(b) ∀u ∈ U_{D} ∀j, j′ ∈ H ∀k ≥ 0(l_{j}^{w}(u)^{j} ∼_{k} l_{j′}^{w}(u)^{j′} ⇔ l_{j}^{v}(u)^{j} ∼_{k} l_{j′}^{v}(u)^{j′})

(c) E_{v}^{n}(l^{v}, D, H).

4. C_{w}(l, D, H) iff ∀n ∈ N E_{w}^{n}(l, D, H).

5. C_{w}(D, H) iff ∃l = (l_{i})_{i∈H} & C_{w}(l, D, H).

If C_{w}(D, H), then we call D common for possibility w.

The condition

∀u ∈ U_{D} ∀j, j′ ∈ H ∀k ≥ 0 (l_{j}^{w}(u)^{j} ∼_{k} l_{j′}^{w}(u)^{j′} ⇔ l_{j}^{v}(u)^{j} ∼_{k} l_{j′}^{v}(u)^{j′})

in the definition of E^{n+1}(l, D, H) is necessary to prove the maximality of the representing DRSes D_{H}^{w^{+}} in G^{+}. The condition implies that for every referent in D_{H}^{w^{+}} it is common information that it was introduced by an observation, or it is common information that it was introduced by the same dialogue participant.

It is useful to define a stronger conditions for joinedness. E_{w}(l, D, H, k) says that all variables in the l_{i}(D)s are chained to subjects in the local DRS of k, k > 0. For k = 0 it says that they are chained to objects in the described situation.

Definition 8.3 Let D be a DRS and w = ⟨𝔄, →, ⟨D_{1}, I_{1}⟩ , …, ⟨D_{m}, I_{m}⟩⟩ ∈ W(G). Let H ⊆ DP, DP = {1, …, m}. Then

1. E_{w}(l, D, H, k) iff

(a) l = l^{(w)} := (l_{i}^{w})_{i∈H} is a family of functions l_{i} : U_{D} ⟶ U_{D_{i}} and D_{i} ⊴_{l_{i}} D,

(b) k ∈ DP,

(c) ∀u_{1}, u_{2} ∈ U_{D} : u_{1} ≠ u_{2} ⇒ ∃i ∈ H : l_{i}(u_{1}) ≠ l_{i}(u_{2}),

(d) ∀i, j ∈ H∃f_{i} : U_{l_{i}(D)} ⟶ U_{D_{k}}

i. ∀u ∈ U_{l_{i}(D)} f_{i}(u)^{k} →_{r} u^{i},

ii. D_{k} ⊴_{f_{i}} l_{i}(D),

iii. ∀u ∈ U_{D} f_{i}(l_{i}(u)) = f_{j}(l_{j}(u)).

2. E_{w}(l, D, H, 0) iff

(a) l = l^{(w)} := (l_{i}^{w})_{i∈H} is a family of functions l_{i} : U_{D} ⟶ U_{D_{i}} and D_{i} ⊴_{l_{i}} D,

(b) ∀u_{1}, u_{2} ∈ U_{D} : u_{1} ≠ u_{2} ⇒ ∃i ∈ H : l_{i}(u_{1}) ≠ l_{i}(u_{2}),

(c) ∀u ∈ U_{D}∀i, j ∈ H ran l_{i/j} ⊆ Obs_{D_{i/j}} & Obs_{D_{i}}(l_{i}(u)) = Obs_{D_{j}}(l_{j}(u)).

Lemma 8.4 1. For i ≠ j u^{i} ∼_{A} v^{j} & u^{i} ∼_{B} v^{j} ⇒ A = B.

2. If φ_{i} ∈ Con_{D_{i}}, φ_{j} ∈ Con_{D_{j}} and

• ∀u ∈ F V (φ_{i})∃v ∈ F V (φ_{j})∃A_{u} u^{i} ∼_{A_{u}} v^{j} and

• ∀v ∈ F V (φ_{j})∃u ∈ F V (φ_{i})∃A_{v} u^{i} ∼_{A_{v}} v^{j},

then all the A_{u}s and A_{v}s are identical.

Proof:

1. i ≠ j implies A ≠ i or A ≠ j. Assume A ≠ i. Then, there is a r ∈ U_{D_{A}} such that r^{A} → v^{i}. If also B ≠ i, then there exists a s ∈ U_{D_{B}} such that s^{B} → v^{i}. Lemma 6.9 implies r^{A} = s^{B}. If B = i, then u^{i} → v^{j} by Lemma 6.7, and therefore u^{i} = r^{A} by Lemma 6.9. Hence A = B.

2. With Lemma 6.9 it follows that φ_{i} and all u ∈ F V (φ_{i}) have been introduced by the same act_{m_{i}}. The same holds for j. Hence, if i = j, the proposition follows directly. Therefore, assume i ≠ j. If m_{i} = m_{j}, then the claim follows with Lemma 6.10. Assume m_{i} < m_{j}. Hence act_{m_{j}} is not an observation, and (act_{m_{j}})_{j} is of the form get(A, G, D). It follows with Lemma 6.9 that i = A.

□

In the following proofs we very often find a situation where some action was performed for a group H, and we want to show that for an agent who does not belong to this group it might be replaced by a sequence of actions where only single persons where involved. Then, we will also find situations where we have two actions where the second depends on the first, and we want to show that for some agent it would be possible that this dependence does not exist. In these cases we can make use of the following remark.

Remark 8.5 (Replacement) Let G ∈ G be given, let a be the sequence of actions which belongs to G. Let s be the initial situation, and γ_{s}(a) the related final possibility.

Assume that a joined act with Obs(H, D, l) is part of the sequence a. If we replace it by a sequence of joined actions with local acts Obs({i}, D, l), one for each participant i ∈ H, then the new final state will be indiscernible from γ_{s}(a) for all j ∈ DP \ H.

In the following we write D_{φ} for the DRS ⟨F V (φ), {φ}⟩. We say that D represents φ iff there exists a φ′ ∈ Con_{D}, and an f : F V (φ′) ⟶ F V (φ) such that φ′/_{s}f = φ.

We want to show that every common DRS for a situation in game G can be embedded into the local representations in G^{+}. We will reach this goal in Theorem 8.11. But before we can proof the theorem we have to show a number of preparatory lemmas.

Lemma 8.6 shows that we can uniquely decompose a joined DRS into the parts which are chained to the environment, or to the various discourse participants.

Lemma 8.6 Let D be a DRS and w = ⟨𝔄, →, ⟨D_{1}, I_{1}⟩ , …, ⟨D_{m}, I_{m}⟩⟩ ∈ W(G). Let H ⊆ DP, DP = {1, …, m}, |H| > 1. Then the following three conditions are equivalent

1. E_{w}(l, D, H)

2. There is exactly one sequence (D_{k})_{k=0,...,m} such that

(a) ⨄_{k=0,...,m} D_{k} = D

(b) ∀k = 0, …, m E_{w}(l, D_{k}, H, k)

3. There is a sequence (D_{k})_{k=0,...,m} such that

(a) ⨄_{k=0,...,m} D_{k} = D

(b) ∀k = 0, …, m E_{w}(l, D_{k}, H, k)

Proof: First, we assume that E_{w}(l, D, H). If ∃x(x →_{r} u^{i} & x →_{r} v^{j}), then Lemma 6.7 implies u^{i} ∼_{0} v^{j} or ∃k ∈ DP u^{i} ∼_{k} v^{j}. Let k ∈ DP. Then we set U_{D_{k}} := {u ∈ U_{D} | ∀i, j ∈ H l_{i}(u) ∼_{k} l_{j}(u)}. By Lemma 8.4 it follows that the U_{D_{k}}s are pairwise disjoint. It shows also that ⟨U_{D_{K}} , Con_{D_{k}}⟩ with Con_{D_{k}} := {φ ∈ Con_{D} | F V (φ) ⊆ U_{D_{k}}} is a proper DRS, and that ⨄_{k∈DP} D_{k} = D.

Let (D′_{k})_{k=1,...,m} be any other decomposition of D. Then it follows by E_{w}(l, D′_{k}, k) that U_{D′_{k}} ⊆ {u ∈ U_{D} | ∀i, j ∈ H l_{i}(u) ∼_{k} l_{j}(u)} = U_{D_{k}}. By ⨄_{k∈DP} D′_{k} = D it follows that D_{k} = D′_{k} for all k ∈ DP.

We define U_{D_{0}} := {u ∈ U_{D} | ∀i ∈ H l_{i}(u) ∈ Obs_{D_{i}}}. For |H| = 1, H = {i} it follows that U_{D_{0}} = dom Obs_{D_{i}}. If |H| > 1, then Lemma 6.7 shows that U_{D_{0}} is disjoint from all U_{D_{k}}, and that ⋃_{k=0,...,m} U_{D_{k}} = U_{D}.

The third condition follows trivially from the second. Hence assume that the third property holds. We need to define suitable functions f : U_{l_{i/j}(D)} ⟶ U_{D_{j/i}}. But we can get them easily from the definitions of E_{w}(l, D_{k}, H, k). □

In the next two lemmas we take a closer look at observations. Let D be a DRS which is common for a group H relative to some l, i.e. C_{w}(l, D, H), and where the referents are jointly chained to the same objects in the described situation, i.e. E_{w}(l, D, H, 0). Then, the two lemmas together show that there is exactly one observation–act by which all the l_{i}(D) have been introduced into the local states of the participants i ∈ H.

Lemma 8.7 Let s be an initial state, a ∈ A(s) and w = γ_{s}(a). Let (D, l) be such that ∀n ∈ N E_{w}^{n}(l, D, H, 0) for a group H ⊆ DP. Let φ ∈ Con_{D}, u ∈ F V (φ). Then there is an act act in a, H′ ⊇ H, D′, l′ and a φ′ ∈ Con_{D′} such that for all j ∈ H φ′/_{s}l′ = φ/_{s}(Obs_{D_{j}} ∘ l_{j}) and act_{j} has the form observe(H′, D′, l′).

Proof: The claim clearly holds for |H| = 1.

Case 1: H = {i, j}. Assume that there is no act act in a with the desired properties. There is a joined act in a with act_{i} of the form observe(H′, D′, l′) such that there is φ′ ∈ Con_{D′} where for i φ′/_{s}l′ = φ/_{s}(Obs_{D_{i}} ∘ l_{i}). Because otherwise φ/_{s}l_{i} can’t be an element of Con_{D_{i}}.

To simplify our proof we concentrate on the case where |F V (φ)| = 1. By our assumption it follows that for all acts act in a of the form observe(H′, D′, l′) we have i ∈ H′ ⇒ j ∉ H′. Let i ∈ H′. (1) Assume further that there is no act′ in a such that act′_{i} is of the form send(i, H′′, D′′, l′′) where φ is represented in Con_{D′′} and j ∈ H′′. Then let a′ be the sequence of actions where all acts act of a where act_{i} is of the form observe(H′, D′, l′) and where φ is represented in D′ are removed. Then, γ_{s}(a′) is indiscernible from w for j. But φ can’t be represented in D_{i}^{γ_{s}(a′)} in such a way that the free variables are elements of Obs_{D_{i}^{γs(a′)}}, therefore D can’t be common. (2) Hence, assume that there

are act^{1/2} in a such that act_{i}^{1} is of the form send(i, H^{1}, D^{1}, l^{1}) where φ is represented in Con_{D^{1}} and j ∈ H^{1}. act_{j}^{2} should be of the related form for j instead of i and 2 instead of 1. Assume that act^{2} is later than act^{1}. Let v be the variable introduced by act^{1} into U_{D_{j}} for φ. Then define l̃ in the same way as l^{2} except for the variables v′ in the representation of φ. Here we define l̃(v′) := v. Then send(j, H^{2}, D^{2}, l̃) would have been a possible action for j in the situation where he performed act^{2}. Hence we may replace act^{2} by this action in a and get a sequence a′. But then γ_{s}(a′) is for i indiscernible from w. We can additionally eliminate all acts with observe(H′, D′, l′) where D′ represents φ and j ∈ H′. For this new sequence a′′ we find also that γ_{s}(a′′) is for i indiscernible from w. But φ can’t be represented in D_{j}^{γ_{s}(a′′)} in a way such that the free variables are elements of Obs_{D_{j}^{γs(a′′)}}. This contradicts the

assumption.

Case 2: |H| = n + 1. We choose some i ∈ H. Let H′ be any set of participants such that i ∉ H′ and where there is an act act with act_{j} of the form observe(H′, D′, l′), j ∈ H′. But then, we can replace these acts by sequences of acts act with act_{j} of the form observe({j′}, D′, l′), j′ ∈ H′. Thereby we get a new sequence a′. We find that for i γ_{s}(a) and γ_{s}(a′) are indiscernible. But by induction it follows that D can’t be common for H′ in γ_{s}(a′).

All other cases follow, if we interchange i and j. □

Lemma 8.8 Let (D, l) be such that C(l, D, H) and E_{w}(l, D, H, 0) for a group H ⊆ DP = {1, …, m} and a possibility w. Then ∀n ∈ N E_{w}^{n}(l, D, H, 0).

Proof: If |H| ≤ 1, then the claim is trivial. Hence, let |H| > 1. Let i ∈ H. Let v be an indiscernible possibility for i in w. Then, there is an l^{v} with E(l^{v}, D, H), l_{i}^{v} = l_{i}^{w} and ∀u ∈ U_{D} ∀j, j′ ∈ H ∀k ≥ 0(l_{j}^{w}(u)^{j} ∼_{k} l_{j′}^{w}(u)^{j′} ⇔ l_{j}^{v}(u)^{j} ∼_{k} l_{j′}^{v}(u)^{j′}). By Lemma 8.6 there is a sequence (D_{k})_{k=0,...,m}, such that ⊎_{k}D_{k} = D and ∀k = 0, …, m E_{v}(l^{v}, D_{k}, H, k). Suppose that U_{D_{k}} ≠ ∅ for a k ≠ 0. Then it holds for all j ∈ H \ {i} and u ∈ U_{D_{k}} that l_{i}^{v}(u)^{i} ∼_{k} l_{j}^{v}(u)^{j} and l_{i}^{w}(u)^{i} ≁_{0} l_{j}^{w}(u)^{j}, which contradicts the properties of l^{v} stated above. Therefore, E(l^{v}, D, H, 0). By induction it follows then that for all n ∈ N E^{n}(l^{v}, D, H, 0).

□

In the next two lemmas we show the existence of two useful partitions of common DRSes.

Lemma 8.9 Let s be an initial state, a ∈ A(s) and w = γ_{s}(a) ∈ W(G). Let (D, l) and H be such that C_{w}(l, D, H).

If there is an k ∈ DP with E_{w}(l, D, H, k), then there is a sequence (D_{r})_{r≤lh(a)} such that:

1. ⨄_{r≤lh(a)} D_{r} = D,

2. if D_{r} is not empty, then it holds for all i ∈ H that for the r–th act act in a act_{i} is of the form get(k, H′, D′) with H′ ⊇ H and D′ ⊴_{f} D_{r} for an injective f.

It follows that E_{w}(l, D, H, k) implies ∀n ∈ N E_{w}^{n}(l, D, H, k), and that l_{i} : U_{D} ⟶ U_{D_{i}} is injective for all i ∈ H \ {k}.

Proof: If H ⊆ {i, k}, then the claim follows from Lemma 6.7. Let H contain at least two agents different from k. By Lemma 6.9 it follows that for all φ ∈ Con_{D}, i ∈ H \ {k} there are D^{i}, H^{i}, and act^{i} such that (act^{i})_{i} is of the form get(k, D^{i}, H^{i}), D^{i} represents φ, i ∈ H^{i}, and such that act^{i} introduced l_{i}(u) for u ∈ F V (φ) into D_{i}. We denote by l_{k}(u) the unique subject in D_{k} such that for all i ∈ H \ {k} l_{k}(u) → l_{i}(u). We show that act^{i} = act^{j} for i, j ∈ H \ {k}. We first show that H^{i} ⊇ H \ {k}. Suppose that there are i, j ≠ k such that for all such acts necessarily i ∉ H^{j} and j ∉ H^{i}. Let u_{0} ∈ F V (φ).

If there is a later send–act by i which depend on the material introduced by act^{i} into his local DRS, then we can include an appropriate observe–act of the form observe({i}, D′, l′) which too could have introduced the relevant material. Lets name this sequence of actions a′. For j we find that γ_{s}(a) and γ_{s}(a′) are indiscernible. We then may remove act^{i} from a′, and get a sequence a′′ such that for j γ_{s}(a′′) is indiscernible from γ_{s}(a′) and γ_{s}(a). But for γ(a′′) there is no referent u_{1} in the local DRS of i such that there is a referent u_{2} in k’s local state such that u_{2}^{k} → u_{1}^{i} and u_{2}^{k} → l_{j}(u)^{j}. Hence, the condition of Def 8.2 for C_{w}(l, D, H) is violated. Therefore, we find H^{i} ⊇ H \ {k}.

Now assume that l_{i/j}(u) was introduced by act^{i/j} into D_{i,j}, and that act^{i} ≠ act^{j}. Assume that act^{j} was later. Then, we can add to the sequence a an act act where i repeats for k what he has heard from k. Hence, this act introduces new subjects (only) into the local DRS D_{k}. Then, we can replace act^{j} by an act act′ where act′_{k} is of the form send(k, D^{j}, H^{j}, l′), and where l′ chains the referents in U_{D} to the referents introduced by act into U_{D_{k}}. We call the new sequence a′. γ_{s}(a) and γ_{s}(a′) are indiscernible for j. But for γ(a′) there is no referent u_{1} in the local DRS of i such that there is a referent u_{2} in k’s local state such that u_{2}^{k} → u_{1}^{i} and u_{2}^{k} → l_{j}(u)^{j}. Hence, the condition of Def 8.2 for C_{w}(l, D, H) is violated again.

Lemma 6.9 shows that act^{i} is unique, and that φ/_{s}l_{i} and all free variables in F V (φ/_{s}l_{i}) have been introduced by this same act. This allows us to define D_{r} as the union of all D_{φ} such that φ/_{s}l_{i} was introduced into the local state of i by the r–th act for some i ∈ H \ {k}.

Finally, we have to show that there exists an injective f such that D′ ⊴_{f} D_{φ} where φ/_{s}l_{i} was introduced into the local DRS D_{i} by an act with act_{i} = get(k, H′, D′), H′ ⊇ H. Let u_{1} ≠ u_{2} ∈ F V (φ). Hence, there exists k′ ∈ H such that l_{k′}(u_{1}) ≠ l_{k′}(u_{2}). If k′ ≠ k, then f exists according to Lemma 6.10. Hence, let k′ = k. But send(k, H′, D′, l′) is licensed only if l′ is injective. Hence, we can find an injective f with D′ ⊴_{f} D_{φ}. By definition of the transition operation τ it follows that for all H ∋ i ≠ k l_{i} : U_{D} ⟶ U_{D_{i}} is injective. □

Lemma 8.10 Let D be a DRS, w = ⟨𝔄, →, ⟨D_{1}, I_{1}⟩ , …, ⟨D_{m}, I_{m}⟩⟩ ∈ W(G). Let H ⊆ DP, DP = {1, …, m}. Let (D, l) be such that C_{w}(l, D, H).

Then there exists a partition (D_{k})_{k=0,...,m} of D such that ∀k = 0, …, m∀n ∈ N E_{w}^{n}(l, D_{k}, H, k).

Proof: By Lemma 8.6 there is partition (D_{k})_{k=0,...,m} of D such that ∀k = 0, …, m E_{w}(l, D_{k}, H, k). The claim follows then from Lemma 8.8 and Lemma 8.9. □

Now we can proof the central result.

Theorem 8.11 Let s be an initial state, a ∈ A(s) and w^{(+)} := γ_{s}^{(+)}(a) in W(G^{(+)}). We set

l^{w} := (l_{i,H}^{w^{+}})_{i∈DP} .

Then, we find:

1. C_{w} (l^{w}, D_{H}^{w^{+}}, H),

2. If C_{w}(l, D, H) for any l, D, then the function f : U_{D} ⟶ U_{D_{H}^{w^{+}}} defined by

f(u) = u′ iff ∃i ∈ H l_{i}(u) = l_{i}^{w}(u′)

is an injection, and f(D) ⊆ D_{H}^{w^{+}}.

Proof: As D_{i}^{w} = D_{i,{i}}^{w^{+}} it follows that l^{w} is well–defined. If l_{i}^{w}(u) = u′ ∈ U_{D_{i}}, then u′ was introduced into D_{i} by an act of the form get(k, H′, D′), H′ ⊇ H \ {k}, or observe(H′, D′, l′), H′ ⊇ H. Furthermore, if u ∈ F V (φ), and φ ∈ Con_{D_{H}^{w^{+}}} , then φ/_{s}l_{i}^{w} was introduced by the same act together with all other free variables. Hence, the local part of act is part of the local states for all i ∈ H. It follows from the definition of the games in G that the same act is part of all local states in CG_{H}(w) (of course, the anchoring function l′ in send(k, H′, D′, l′) for the speaker k may vary). This allows us to define simultaneously the embedding functions l^{v} for all v ∈ CG_{H}(w). We can prove then that for all v E^{v}(l^{v}, D, H), and that the conditions of Definition 8.2 hold. This proves the first part of the theorem.

Let (D, l) be such that C_{w}(l, D, H). Lemma 8.10 shows that there is a decomposition (D_{k})_{k≥0} of D such that for all k ≥ 0 and n ∈ N E_{w}^{n}(l, D_{k}, H, k), and such that ⨄_{k≥0} D_{k} = D. For k = 0 Lemma 8.7 shows that for every φ ∈ Con_{D} there is an act in a where act_{i} is of the form observe(H′, D′, l′) for i ∈ H ⊆ H′ and such that φ′/_{s}l′ = φ/_{s}(Obs_{D_{i}} ∘ l_{i}). Hence, there must be an act where act_{i} is of the form observe(H′′, D′′, l′′) for i ∈ H ⊆ H′′ and where φ′/_{s}l′ = φ′′/_{s}l′′, and which introduced φ′′′ into D_{H}^{w^{+}} with φ′′′/_{s}(Obs_{D_{i}} ∘ l_{i,H}^{w^{+}}) = φ′′/_{s}l′′. This shows that f(u) := u′ iff ∃i ∈ H l_{i}(u) = l_{i}^{w}(u′) is an injection on U_{D_{0}} with f(D_{0}) ⊆ D_{H}^{w^{+}}.

Let (D_{r})_{r≤lh(a)} be the sequence constructed in Lemma 8.9. If D_{r} is not empty, then the r–th act act of a has the property that for some i ∈ H act_{i} is of the form get(k, H′, D′), H′ ⊇ H \ {k} with D′ ⊴_{f} D_{r} for an injective f. We find for u ∈ U_{D} a unique u_{0} in some D′ such that for all i ∈ H l_{i}(u) is the discourse referent introduced by u_{0}. We find also that u ∈ F V (φ), φ ∈ Con_{D}, implies that φ/_{s}l_{i} was introduced into the local DRS of i by the same act. But this act introduces for u_{0} and φ exactly one referent u′ into D_{H}^{w+}, and l_{i}^{w} maps u′ back to the referent introduced by u_{0} into D_{i}^{w}. Hence, l_{i}(u) = l_{i}^{w}(u′), for each u ∈ U_{D} there is exactly one such u′, and it is the same for all i ∈ H. As distinct referents in D′ introduce distinct referents into D_{H}^{w^{+}}, it follows that f(u) := u′ iff l_{i}(u) = l_{i}^{w}(u′) defines an injective function. Lemma 6.10 and the construction of τ for G^{+} shows also that f(D) ⊆ D_{H}^{w^{+}}. □

9 Final Remarks and Conclusions

In Section 4 we promised to show the following properties of common DRSes and their internal representations:

1. The set of common DRSes has maximal elements.

2. The maximal common DRSes are identical up to substitutions of variables.

3. The representing DRS for a group H is a maximal common DRS for this group.

We can now make these statements precise. Let s be an initial situation, a ∈ A(s) a sequence of actions, H ⊆ DP a group, and w = γ_{s}(a), w^{+} = γ_{s}^{+}(a). Then, let C_{w}(H) := {D ∈ DRS | C_{w}(D, H)} be the set of all common DRS for group H in w, and D ≤ D′ iff ∃f : U_{D} ⟶ U′_{D} inj. : f(D) ⊆ D′. ≤ is a pre–order on C_{w}(H). It defines a order on the equivalence classes [D] := {D′ ∈ C_{w}(H) | D ≤ D′ & D′ ≤ D}. Then:

1. (C_{w}(H), ≤) has maximal elements.

2. The maximal elements are unique up to substitution of variables, i.e. for maximal DRSes D and D′ there are bijective functions f : U_{D} ⟶ U_{D′} such that f(D) = D′.

3. D_{H}^{w^{+}} is a maximal DRS in (C_{w}(H), ≤).

This follows directly from Theorem 8.11. Furthermore, we should note that:

1. ∀v ∈ CG_{w}(H) CG_{v}(H) = CG_{w}(H).

2. ∀v ∈ W(G) : v ∈ CG_{w}(H) ⇒ C_{v}(H) = C_{w}(H).

3. ∀v^{+} ∈ W(G^{+}) : v^{+} ∈ CG_{w^{+}}(H) ⇒ D_{H}^{v^{+}} = D_{H}^{w^{+}}.

4. ∀s′, a′ : γ_{s′}(a′) ∈ CG_{w}(H) ⇒ γ_{s′}^{+}(a′) ∈ CG_{w^{+}}(H).

The directions ⇐ don’t hold in general. This is due to the additional information about the actions in a which is available in the local states in the games in G.

The proofs in the last sections depend very much on the concrete definitions of the multi–agent systems for G and G^{+}. Hence, it is dubious whether the results generalise for more complex and restricted fragments of dialogue. Our fragment allows e.g. for repeated statements of the same facts. This allows for the introduction of a lot of superfluous discourse referents. E.g. assume that the described situation contains only one object, and that everybody who observes this scene knows that it must be common knowledge for all observers that there is only this one. Assume it is a broken drinking glass. Then, repeated statements of there is a broken drinking glass will introduce for every utterance a new referent which represents this glass into the common DRSes. But the available visual information will make clear that there is only one broken drinking glass:

(6) Anne enters a room. Last night, there has been a party. There is a table, and on the table there is a broken drinking glass.

Anne: I have just been in the room there. Have you been there too? Did you have a look at the table?

Bob: Yes, I did.

Anne: The broken drinking glass is there from the party last night.

Anne’s use of the broken drinking glass seems to be ok. But, of course, no common discourse referent is available at this point of time. This shows a clear limitation of our approach. There are, of course, more sources of additional information which can not be handled by our theory.

Conclusions

We are able to represent the chains that are defined by iterated specific uses of indefinite NPs. The theory of multi–agent systems, which builds the basis for our model, provides us with natural descriptions of the common ground as an information state representing mutual information. In order to explain the referential anaphoric use of a definite description, and especially how to apply it’s uniqueness condition, we found that this use is sensitive to common substructures of the local states of discourse participants. We characterised them as common DRSes and explained how the participants can represent these common DRSes.

• Specifically used indefinite NPs introduce free variables. The interpretation function, which is necessary to define the truth values for the conditions of a DRS, are provided by an external chain relation. They never get existentially bound.

• There are three distinct objects in our model which are possible representations for the linguistic common ground: (1) The information states representing common knowledge, (2) the common DRSes, and (3) the internal representations of the common DRSes.

• The uniqueness condition connected to an anaphorically used definite description does not contribute to the asserted meaning of a sentence. If a speaker uses a description of the form defx.φ(x), then this use presupposes that there is an object a such that φ(a) holds.

References

P. Aczel (1988): Non–Well–Founded Sets; CSLI–Lecture Note 14, Stanford.

A. Benz (1999): Perspectives and the Referential Use of Definite Descriptions in Dialogue; ms., Berlin.

H.H. Clark, C.R. Marshall (1981): Definite Reference and Mutual Knowledge; in: A.K. Joshi, B. Webber, J. Sag (ed.): Elements of Discourse Understanding, Cambridge University Press, Cambridge.

P. Dekker (1997): On First Order Information Exchange; in: A. Benz & G. Jäger (ed.), Proceedings of the Munich Workshop on Formal Semantics and Pragmatics of Dialogue MunDial’97, CIS Lecture Notes 106, München, pp. 21–39.

P. Dekker (2000): Meaning and Use of Indefinite Expressions – The Exchange of Open Propositions; Journal of Logic, Language and Information, 9.

P. Dekker, R. v. Rooy (1999): Intentional Identity and Information Exchange; ms, ILLC/University of Amsterdam.

R. Fagin, J.Y. Halpern, Y. Moses, M.Y. Vardi (1995): Reasoning About Knowledge; MIT–Press, Cambridge, Massachusetts.

J. Gerbrandy, W. Groeneveld (1997): Reasoning about Information Change; Journal of Logic, Language and Information 6, p.147–169.

J. Gerbrandy (1998): Bisimulations on Planet Kripke; ILLC Dissertation Series, Institute for Logic, Language and Computation, Universiteit van Amsterdam.

H. Kamp, U. Reyle (1993): From Discourse to Logic; Kluwer, Dordrecht.

J. v. Eijck, H. Kamp (1997): Representing Discourse in Context; in: J. v. Bentham, A. t. Meulen Handbook of Logic & Language, Elsevier, Amsterdam.

Contents

1 Introduction 1 1.1 Referential Chains . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Definite Reference and the Common Ground . . . . . . . . . . . 3

I The Description of the Theory 4

2 A Dialogue Fragment with Referential Chains 5 2.1 The Basic Idea for the Representation of Dialogue Situations . . 5 2.2 The Representation as Multi–Agent System . . . . . . . . . . . . 6

2.2.1 Global States . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 The Possible Dialogue Acts . . . . . . . . . . . . . . . . . 7 2.2.3 When do we Allow to Perform a Joined Action? . . . . . 8 2.2.4 The Effects of Performing an Action . . . . . . . . . . . . 9

2.3 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 The Uniqueness Condition for Definite Descriptions 11 4 The Representation Problem 14

II The Mathematics of the Theory 15

5 Basic Definitions 16 6 A Dialogue Fragment with Referential Chains 18 7 A Fragment with Representations for Common DRSes 25 8 Common DRSes 27 9 Final Remarks and Conclusions 34