Towards a Framework for Bidirectional Optimality Theory in Dynamic Contexts

Anton Benz^{∗}

             toni.benz@german.hu-berlin.de

Abstract In this paper we study context–sensitive versions of bidirectional Optimality Theory (OT). We discuss a problem presented by Jason Mattausch which shows that context–sensitivity may lead into circularity. In order to be able to represent it we introduce a fundamental structure for bidirectional OT which we call Blutner structure. The discussion of Mattausch’s Example leads us to combine bidirectional OT with Dynamic Semantics.

1 Introduction

Bidirectional Optimality Theory (OT)^{1} has been suggested as a framework which explains how speaker and interpreter co-ordinate their choice of preferred forms and preferred interpretations. Recently^{2} this theory has been applied to anaphora resolution. In an example like (1) the theory explains why it is the best way to refer to Marion and Jo with she and his:

(1) Marion was frustrated with Jo. She/Marion/the girl was pulling his/Jo’s/ the boy’s hair out.

If we assume that it is more economic for the speaker to produce a pronoun than a name, and better to repeat the same name than to produce a definite description, and if we assume that the hearer prefers an interpretation where Marion denotes a female and Jo a male person, then she and his are the optimal choices for referring back to Marion and Jo. The aim of our paper is to outline a framework which describes the reasoning of bidirectional OT in contexts known from Dynamic Semantics.

In bidirectional OT it is cammon to assume that there is a set F of forms, and a set M of meanings (Blutner, 2000). The speaker has to choose for his next utterance a form which then must be interpreted by the hearer. It is further assumed that the speaker has some ranking on his set of forms, and the hearer on the set of meanings. Blutner (2000) introduced the idea that the speaker and interpreter co-ordinate on form–meaning pairs which are most preferred from both perspectives. In (Jäger, 2000) the mechanism which leads to optimal form–meaning pairs is discussed in greater detail^{3}. The speaker has to choose for a given meaning M_{0} a form F_{0} which is optimal according to his ranking of forms. Then the interpreter has to choose for F_{0} a meaning M_{1} which is optimal according to his ranking of meanings. Then again the speaker looks for the most preferred form F_{1} for M_{1}. A form–meaning pair is optimal, if ultimately speaker and hearer choose the same forms and meanings. If ⟨F, M⟩ is optimal in this technical sense, then the choice of F is the optimal way to express M such that both speaker’s and interpreter’s preferences are matched.

∗This paper was written in spring 2001; last minor corrections March 2003

1(Blutner, 1998, 2000; Blutner, Jäger, 2000; Zeevat, 2000; Beaver, 2000)

2(Beaver, 2000). Beaver’s version of a two–sided OT is in some respects different from the version cited above.

The following example presented by Jason Mattausch (2000, pp. 33–36) shows that there is no guarantee that optimal form–meaning pairs exist:

(2) Assume that Marion is a male person, and Jo a female one. The speaker wants to express with the second sentence that Jo was pulling Marion’s hair out:

a) Marion was frustrated with Jo. She was pulling his hair out.

b) Marion was frustrated with Jo. He was pulling her hair out.

c) Marion was frustrated with Jo. Jo was pulling Marion’s hair out.

Intuitively, c) is the right way to put it. Mattausch assumes that pronouns have to agree with the natural gender of the person referred to, and that pronouns are preferred over names. On the other side, the hearer prefers an interpretation where Marion is female, and Jo male. These constraints lead into the following circle:

The speaker starts with the meaning pulling–hair–out(Jo, Marion), hence, he has to choose She was pulling his hair out. The hearer will interpret this form according to his preferences as pulling–hair–out(Marion, Jo). But this content should be expressed by the speaker as He was pulling her hair out. For this form the hearer should prefer the interpretation pulling–hair–out(Jo, Marion). And here the circle closes.

We never reach a situation where speaker and hearer will always choose the same form and meaning. This means that bidirectional OT can’t provide for an optimal form–meaning pair, and if the speaker wants to communicate that Jo was pulling Marion’s hair out, then it fails to predict that exactly this sentence is the optimal one. Mattausch then argues that we have to give up bidirectional OT in the style of (Blutner, 2000). We want to show that such a conclusion is premature. For that we have to outline how to apply bidirectional reasoning in contexts known from Dynamic Semantics. The problems behind Mattausch’s Example will lead us on our way.

The example shows that there may exist circular structures. Gerhard Jäger (2000, Lem. 2) shows that no circularity can arise as long as we assume that preferences are induced by a system of ranked OT–constraints. This result leads him to use OT–systems as they have been introduced for unilateral OT as underlying structures for bidirectional OT. They are pairs ⟨Gen, C⟩ where Gen represents a set of grammatical form–meaning pairs, and C a set of functions representing a system of ranked constraints. If we use them as fundamental structures, then circularity is ruled out a priori. Although we will show that the circularity in Mattausch’s Example is only apparent, we think that OT– structures should be flexible enough to represent it. We will see that it can’t be generated by OT–systems because all constraints are ranked in one line. If we divide them into constraints for the speaker and constraints for the interpreter, and rank them separately, then we can avoid this limitation. We introduce structures — we call them Blutner structures — which allow to represent Mattausch’s Problem for anaphora resolution, and to solve it within bidirectional OT. Our examples show that we need constraints which are not only sensitive to forms and meanings but also to some facts about the real world. This leads us to consider Blutner structures with arbitrary context–sensitive constraints. These facts may have been introduced by previous discourse. Our aim is to integrate bidirectional OT into (a fragment of) Dynamic Semantics. We will first introduce the static part, then apply this framework to Mattausch’s Example, motivate thereby the modifications for dynamic contexts, and define them precisely in the last section.

3We describe the procedure which provides for a strong z–optimal form–meaning pair.

(Blutner, 1998, 2000) introduced in addition weak optimality, also called superoptimality, see (Jäger, 2000, p.45).

We discuss OT–systems in more detail in Section 2. In Section 3 we introduce Blutner structures which are generated by two OT–systems over the same set of grammatical form–meaning pairs. There we have to show that central notions of bidirectional OT like optimality and weak optimality can be generalized for these structures, how these structures are related to OT–systems, and how we can handle arbitrary context–sensitive constraints.

In Section 4 we will use Blutner structures to study Mattausch’s Example. It turns out that when switching from the speaker’s to the interpreter’s role we have to be cautious about the contexts and the information the hearer has about contexts. It may well be that the interpreter prefers for a given form a meaning which is only grammatical in a context different from the actual one. Exactly this happens in Mattausch’s Example. If we then switch to the speaker’s role again, it follows that he can’t find an appropriate form for this meaning. We call such a situation a dead end. We argue that we have to add to context– dependent bidirectional OT a principle which postulates that the speaker has to avoid forms which necessarily lead into dead ends.

This shows that it is essential for Mattausch’s Example that the interpreter has only a limited knowledge about the actual context. In a Dynamic Semantic setting we can assume that he always has less information than the speaker. Hence, he has more form–meaning pairs to consider — all the form–meaning pairs which are grammatical in any of his epistemically possible contexts. We assume that these epistemic possibilities are given by the information state defined by the previous discourse. We will introduce Blutner structures for dynamic contexts in Section 5. This leads us to a system which allows to integrate bidirectional OT and Dynamic Semantics.

2 OT–Systems

According to OT, producer and interpreter of language use a number of constraints which govern their choice of forms and meanings. These constraints may get into conflict. OT proposes a mechanism for how these conflicts are resolved. It assumes that the constraints are ranked in a linear order. If they get into conflict, then the higher-ranked constraints win over the lower ranked. This defines preferences on forms and meanings.

Preferences can be identified with transitive relations ⪯, where we read F ≺ F′ as F′ is preferred over F, and F ≈ F′ as F and F′ are ranked equal. We first fix some terminology concerning transitive relations:

Definition 2.1 Let M be a set and ⪯⊆ M × M a relation. We say that ⪯ is a pre–order, iff

• m ⪯ m,

• m ⪯ m′ ∧ m′ ⪯ m′′ ⇒ m ⪯ m′′.

⪯ is an order, iff in addition

• m ⪯ m′ ∧ m′ ⪯ m ⇒ m = m′.

If ⪯ is a pre–order, then the sets [m] := {m′ ∈ M | m ⪯ m′ & m′ ⪯ m} are equivalence classes. If we set [m] ⪯ [m′] ⇔ m ⪯ m′, then ⪯ is an order relation on the set of equivalence classes [m].

An order ⪯ is linear, iff

m ⪯ m′ ∨ m′ ⪯ m.

It is well founded, iff there is for every set X ⊆ M an m ∈ X such that

∀m′ ∈ X (m′ ⪯ m ⇒ m′ = m).

We call a pre–order well–founded or linear, iff the associated order on the set of equivalence classes {[m] | m ∈ M} is well–founded or linear.

A constraint can be represented most naturally by a formula φ(v_{1}, …, v_{n}) with free variables. This is equivalent with a representation as a binary valued function c with n argument positions, where c(a_{1}, …, a_{n}) = 0 iff φ(a_{1}, …, a_{n}) holds, and c(a_{1}, …, a_{n}) = 1 iff φ(a_{1}, …, a_{n}) does not hold. If we assume in addition that a constraint does also rank the tuples ⟨a_{1}, …, a_{n}⟩, then we can identify it with a function c which maps ⟨a_{1}, …, a_{n}⟩ into the set of natural numbers N. If we concentrate on form–meaning pairs, then c should be defined on a set Gen of pairs ⟨F, M⟩ which are generated by the rules of an underlying grammar. These constraints induce a ranking on Gen.

We can bring these parts together. The resulting structure is called OT– system^{4}:

Definition 2.2 (OT–System) An OT–system is a pair O = ⟨Gen, C⟩, where Gen is a relation, and C = (c_{α})_{1≤α<β} is a sequence of functions from Gen to N, β an ordinal number.

1. Let a ≈_{O} b iff for all α < β c_{α}(a) = c_{α}(b).

2. Let a, b ∈ Gen. a <_{O} b iff there is an γ with 1 ≤ γ < β such that c_{γ}(a) < c_{γ}(b) and for all α < γ : c_{α}(a) = c_{α}(b).

We write a ≤_{O} b for a ≈_{O} b ∨ a <_{O} b.

4We follow (Jäger, 2000, Def. 4)

For technical reasons the preference relation is read here in inverse order, i.e. a <_{O} b means that a is preferred over b. This implies that c_{1} is the strongest constraint, then comes c_{2}, etc.

Jäger (2000) suggests that these structures underlie also bidirectional OT. The two–sidedness of bidirectional OT is captured by a difference in the constraints. There are two important classes, the class of input markedness constraints, and the class of output markedness constraints^{5}.

Definition 2.3 Let O = ⟨Gen, C⟩ be an OT–system.

• A constraint c is an output markedness constraint, iff

⟨F, M⟩ , ⟨F′, M⟩ ∈ Gen ⇒ c(⟨F, M⟩) = c(⟨F′, M⟩).

• A constraint c is an input markedness constraint, iff

⟨F, M⟩ , ⟨F, M′⟩ ∈ Gen ⇒ c(⟨F, M⟩) = c(⟨F, M′⟩).

An advantage of this move is that it allows to generalise results known for one–sided OT to bidirectional OT, which is the concern of Jäger’s paper.

Jäger shows that the ranking relation <_{O} on Gen is well–founded for all OT–systems.

Lemma 2.4 Let O be an OT–system. Then ≤_{O} is a linear and well–founded pre–order.

Proof: It is clear that ≤_{O} is linear, and that it is a pre–order. Assume that there exists (a_{n})_{n∈ω} such that ∀n a_{n+1} <_{O} a_{n}. Let γ′_{n} := min{γ < β|c_{γ}(a_{n+1}) < c_{γ}(a_{n})} and γ_{n} := ωγ′_{n}+c_{γ′_{n}}(a_{n}). It is clear that all γ_{n} exist and that γ_{n+1} < γ_{n}. But this contradicts the well–foundedness of the ordering of ordinals. □

This implies that we can never represent a Mattausch square in ⟨≤_{O}, Gen⟩:

⟨F_{1}, M_{1}⟩ ⟵ ⟨F_{2}, M_{1}⟩
↓  ↑
⟨F_{1}, M_{2}⟩ ⟶ ⟨F_{2}, M_{2}⟩

Where the form–meaning pairs are as follows:

⟨F_{1}, M_{1}⟩ := ⟨She was pulling his hair out, pulling–hair–out(j, m)⟩
⟨F_{1}, M_{2}⟩ := ⟨She was pulling his hair out, pulling–hair–out(m, j)⟩
⟨F_{2}, M_{1}⟩ := ⟨He was pulling her hair out, pulling–hair–out(j, m)⟩
⟨F_{2}, M_{2}⟩ := ⟨He was pulling her hair out, pulling–hair–out(m, j)⟩

Mattausch postulates the following constraints in order to generate this square:

1) Pronouns have to agree with the natural gender of the person referred to.

2) Pronouns are preferred over names. 3) The interpreter prefers a default interpretation concerning the gender of the bearer of names.

We first see that neither 1) nor 3) are input or output markedness constraints in the sense defined above. Nevertheless, they are natural constraints and should not be excluded from bidirectional OT. The definitions above imply that the function c ∈ C depends either on F or on M. Hence, they have in fact only one true argument. The first thing we can learn is that the two–sidedness of bidirectional OT should not be regarded as a restriction on the type or number of arguments. But even if we do not restrict the class of constraints, we get only well–founded orders ≤_{O} on Gen. We think that OT should allow for the representation of Mattausch squares. If so, then OT–systems can not be the right structures.

5(Jäger, 2000, p. 54–55)

Reconsidering the constraints used by Mattausch we see that they naturally divide into group 1), 2) of constraints responsible for the choice of a from F by a speaker, and constraint 3) which governs the choice of a meaning M by the interpreter. The preferences for forms depend on a meaning argument, and the choice of meanings on a form argument. Hence the constraints for the speaker induce a preference relation ⪯_{M} for each meaning between forms, and those for the interpreter a preference relation ⪯_{F} for each form between meanings. We collect these parts in a structure which we will call Blutner structure. We study them in the next section.

It is of course not clear from the outset that these structures improve over OT–systems. But as they allow for the representation of Mattausch squares it is clear that they can’t be reduced to OT–systems. We will show that Blutner structures are essentially generated by two OT–systems, one for the producer, and one for the interpreter. This gives us also an intuitive reason why OT– structures don’t allow for circularity. We assume for the sake of the argument that all four form–meaning pairs are grammatical in the given situation. Of course, all four form–meaning pairs pass the test with the second constraint. Hence, we need only consider 1) and 3). First we assume that the constraints are ordered as 1) < 3), i.e. a pair ⟨pronoun, person⟩ is better for a fixed utterance context w if the gender of the pronoun agrees with the real sex of the person, than if the pronoun agrees only with the expected sex of this person. This implies that the hearer has to check at a crucial point a speaker’s constraint: The speaker wants to express that M_{1}. As ⟨F_{2}, M_{1}⟩ fails the test with constraint 1), it follows that it is outranked by ⟨F_{1}, M_{1}⟩, which violates only the third constraint. Then we take the perspective of the interpreter. He again has to check all three constraints. And this means that he has to check whether the pronoun agrees with the natural gender of the person referred to. But this also means that he first has to know that the pronoun has to agree with the gender of Jo, and that he has to know that Jo is a woman. But this presupposes that he has to have access to the speaker’s knowledge. He can’t check constraint 1)! If we invert the order of constraints and assume that 3) < 1), then we face a similar problem for the speaker. At a crucial point he has to check an interpreter’s constraint: If he chooses between F_{1} and F_{2} in order to express M_{1}, he will first test with 3) and get F_{2} as optimal form. But intuitively this form should be outranked by his preference for 1).

These considerations show that we have to consider the effect of the interpreter’s partial knowledge. In a Dynamic Semantics framework we can identify the hearer’s knowledge with the information introduced by the previous discourse. Hence, this will play a role if it comes to integrating bidirectional OT and Dynamic Semantics. But first we introduce Blutner structures for static contexts. The detailed discussion of Mattausch’s Example in Section 4 will then motivate the necessary modifications for dynamic contexts.

3 Blutner Structures

In the last section we have seen that it is desirable to look for structures which make the idea explicit that the constraints divide into one ranked group which provides for the speaker’s preferences on forms, and a second ranked group which provides for the hearer’s preferences on meanings. We call these structures Blutner structures. If these structures shall be acceptable, we have to show that we can model the usual reasoning in bidirectional OT with these structures. Therefore, we have to generalise the definitions of optimality and weak optimality. We essentially copy the explications of Jäger (2000). We then show how these structures are related to OT–systems. Especially, we show that they are generated by two OT–systems over the same set of grammatical form– meaning pairs, one system for the speaker and one system for the interpreter. Finally, we show how to represent arbitrary context–sensitive constraints within this framework.

Blutner Structures

OT–systems are pairs ⟨Gen, C⟩, where Gen is a set of form–meaning pairs which is generated by a given grammar. We use the same underlying structure but make the set of forms F and meanings M explicit, i.e. the underlying structure has the form ⟨F, M, Gen⟩. The following definition of Blutner structure can be motivated by the way how speaker and interpreter find an optimal form–meaning pair. As explained in the introduction, the speaker starts with a meaning M and searches a grammatical form F for this meaning which fits best to his preferences. This means that he has to search for a fixed M the set

R(M) := {F | ⟨F, M⟩ ∈ Gen}.

Then, his preferences must rank the elements in this set, i.e. they must define a binary relation ⪯_{M} on R(M). We assume that ⪯_{M} is at least a linear pre–order. A symmetric assumption has to be made for the interpreter. If we collect all the preference relations ⪯_{M} and ⪯_{F}, then we end up with structures of the following type:

Definition 3.1 (Blutner Structure) A Blutner structure is a tuple B = ⟨F, M, Gen, ⪯⟩ where

• F and M are disjoint sets.

• Gen is a subset of F × M.

• ⪯ is a family (⪯_{p})_{p∈P} where P ⊆ F ∪ M, and:

– ⪯_{F} is a linear pre–order on {M | ⟨F, M⟩ ∈ Gen}, F ∈ F.

– ⪯_{M} is a linear pre–order on {F | ⟨F, M⟩ ∈ Gen}, M ∈ M.

We use the following terminology: We call B a two–sided Blutner structure, iff P = F ∪ M. If P = F, then we call B M–sided, and if P = M, then F–sided. We call F a set of forms, and M a set of meanings.

Of course, F and M may denote any sets of objects. In case of Mattausch’s Example we will define F as the set of sentences of natural language, and the set M as the set of their translations into a language of formal logic. The speaker has to choose an object F in F for an M ∈ M, and the interpreter has to choose some object M in M for an F ∈ F. We assume that they can only choose an F, or an M, if the resulting form–meaning pair ⟨F, M⟩ is an element of Gen, i.e. if it is grammatical. Now, we claimed that Blutner structures make the idea explicit that constraints divide into a group which provides for the speaker’s preferences on forms, and one group which provides for the hearer’s preferences on meanings. It may seem that this is not captured by the definition above because there it is assumed that for the speaker there exists for every form F a preference relation on meanings, and that for the interpreter there exists for every meaning a preference relation on forms. At first sight this is much more fine–grained. But we will see in Lemma 3.7 that Blutner structures are really generated by two ranked sequences of constraints provided that the inverse relations of ⪯_{F} and ⪯_{M} are all well–founded.

Optimality and Weak Optimality

We first want to show that some central notions of bidirectional OT can be redefined for Blutner structures. ⪯ induces a pre–order ≤ on Gen. It is the (inverse) counterpart to the order ≤_{O} induced by an OT–system.

Definition 3.2 Let B = ⟨F, M, Gen, ⪯⟩ be a Blutner structure. Then we can define a pre–order ≤ on Gen × Gen if we build the transitive closure of the relation defined by: ⟨F, M⟩ ≤ ⟨F′, M′⟩ iff

(F = F′ & M ⪯_{F} M′) ∨ (M = M′ & F ⪯_{M} F′).

Clearly, we can find a Blutner structure which allows us to represent a Mattausch square in the associated ⟨≤, Gen⟩. This implies that in general we can’t generate ⟨≤, Gen⟩ by an OT–system. We will show how to generalise the usual Blutner–Jäger definitions for optimality and weak optimality to Blutner structures.

Definition 3.3 (Optimality) Let B = ⟨F, M, Gen, ⪯⟩ be a Blutner structure, and ⟨≤, Gen⟩ the associated pre–order. A pair ⟨F, M⟩ ∈ Gen is optimal, iff it is a maximal element in ⟨≤, Gen⟩.

Optimality is a central notion of bidirectional OT because bidirectional OT makes the assumption that speakers and interpreters agree to choose only optimal form–meaning pairs, or weakly optimal form–meaning pairs. That they choose optimal form–meaning pairs can be expected from general considerations about rationality. Weak optimality is the empirically more interesting notion because its implications are less expected. But it will play no role in our future considerations. Therefore, we just show that the usual definition of Blutner and Jäger can be generalised for Blutner structures. For more motivation we refer to (Blutner, 2000). The crucial condition for weak optimality is that of Def. 3.4.

Definition 3.4 (Weak Optimality Set)

Let B = ⟨F, M, Gen, ⪯⟩ be a Blutner structure.

A Set S ⊆ Gen is a weak optimality set, iff for all ⟨F, M⟩ ∈ Gen ⟨F, M⟩ ∈ S implies that the following two conditions hold

1. there is no pair ⟨F′, M⟩ ∈ S such that F ≺_{M} F′,

2. there is no pair ⟨F, M′⟩ ∈ S such that M ≺_{F} M′.

Intuitively, a pair ⟨F, M⟩ is weakly optimal, iff there is no weakly optimal ⟨F′, M⟩ or ⟨F, M′⟩ which is preferred by one of the interlocutors. As it stands, this definition is circular, and, in fact, there are many sets S which have the property of Definition 3.4. We show that we can construct a weak optimality set. We can start with the set of optimal form–meaning pairs, then take away all pairs which are immediately dominated by an optimal form–meaning pair (the first part of the disjunction in the following definition of D_{α}), and add then the new set of optimal pairs. This process can be repeated until no new optimal form–meaning pairs emerge. It is possible to extend the process even beyond this point (here we need the second part of the disjunction as well), but the choice of new elements for S is absolutely arbitrary.

Lemma 3.5 Let B = ⟨F, M, Gen, ⪯⟩ be a Blutner structure, and ⟨≤, Gen⟩ the associated pre–order.

1. The set of optimal elements is a weak optimality set.

2. Every weak optimality set can be extended to a maximal weak optimality set by the following construction:

Let S_{0} be any weak optimality set, Gen_{0} := Gen, and for α > 0 we set:

(a) S_{<α} := ⋃_{β<α} S_{β},

(b) D_{α} := {⟨F, M⟩ ∈ Gen | ∃ ⟨F′, M′⟩ ∈ S_{<α} : (F = F′ ∨ M = M′) ∧ (⟨F, M⟩ ≤ ⟨F′, M′⟩ ∨ ⟨F′, M′⟩ ≤ ⟨F, M⟩)},

(c) Gen_{α} := Gen \ D_{α},

(d) S_{α} := S_{<α} together with some arbitrary element of Gen_{α}, if there is one.

3. If we start the construction with the set of all optimal elements, and replace S_{α} by

S_{α} := S_{<α} together with the set of optimal elements for ⟨≤, Gen_{α}⟩ ,

then the maximal set WOT which we can construct in this way is a weak optimality set, and it is the intersection of all weak optimality sets which extend WOT.

Proof: That the set of optimal elements is a weak optimality set follows trivially by definition.

For 2: The union ⋃_{β<α} S_{β} and all S_{α} are weak optimality sets. This follows directly by definition. Furthermore, β < α implies S_{β} ⊆ S_{α}. It follows by the Lemma of Zorn that we ultimately find a maximal weak optimality set.

For 3: That WOT is a weak optimality set follows by induction over α. Assume that S is a weak optimality set which extends WOT . Let ⟨F, M⟩ ∈ S \ WOT . Then, there is no ⟨F′, M′⟩ ∈ WOT such that (F = F′ ∨ M = M′) ∧ (⟨F, M⟩ ≤ ⟨F′, M′⟩ ∨ ⟨F′, M′⟩ ≤ ⟨F, M⟩), and ⟨F, M⟩ can’t be an optimal element for ⟨⪯, Gen_{∞}⟩, where we set D_{∞} := {⟨F, M⟩ ∈ Gen | ∃ ⟨F′, M′⟩ ∈ WOT : (F = F′ ∨ M = M′) ∧ (⟨F, M⟩ ≤ ⟨F′, M′⟩ ∨ ⟨F′, M′⟩ ≤ ⟨F, M⟩)}, and Gen_{∞} := Gen \ D_{∞}. Hence, there must exist a ⟨F′, M′⟩ ∈ Gen_{∞} (F = F′ ∨ M = M′) ∧ (⟨F, M⟩ ≤ ⟨F′, M′⟩). As ⟨F′, M′⟩ ∈ Gen_{∞} we can start with WOT , choose ⟨F′, M′⟩, and construct a maximal weak optimality set S′. But ⟨F, M⟩ ∉ S′ by definition of D_{∞+1}, hence, ⟨F, M⟩ ∉ S ∩ S′. □

Definition 3.6 (Weak Optimality)

We call a form–meaning–pair ⟨F, M⟩ weakly optimal for a Blutner structure B = ⟨F, M, Gen, ⪯⟩, iff ⟨F, M⟩ is an element of WOT.

Blutner Structures and OT–Systems

Now we want to show how Blutner structures are related to underlying OT– systems. We will see that every Blutner structure B = ⟨F, M, Gen, ⪯⟩ where the inverse of ⪯_{F} and ⪯_{M} are well–founded relations can be generated by two OT–systems over the same set of grammatical form–meaning pairs, i.e. they are generated by pairs ⟨O_{F}, O_{M}⟩ of OT–systems O_{X} = ⟨Gen, C_{X}⟩. As both systems have the same set Gen they differ only with respect to the sequence C of constraints. The construction below shows that C_{F} is responsible for the definition of the preferences ⪯_{M} on F, and C_{M} for the preferences ⪯_{F} on M. But this means that the interpreter’s preferences for meanings are defined by a sequence of constraints, and the speaker’s preferences for forms by a separate sequence. This shows that Blutner structures really incorporate the idea that preferences are defined relative to two separate sequences of constraints, one for the speaker and one for the interpreter. We will see in the next section that we have to weaken the condition that both OT–systems are defined over the same set Gen if we want to capture dynamic contexts.

We first show how OT–systems over a fixed set Gen of form–meaning pairs generate Blutner structures. Let O = ⟨Gen, C⟩ be an OT–system over a set of form–meaning pairs Gen ⊆ F × M with C = ⟨c_{α}⟩_{α<β}. We can then use the result of Jäger to define for each M ∈ M and F ∈ F an associated linear well–founded pre–order <_{O_{M}} on R(M) := {F ∈ F | ⟨F, M⟩ ∈ Gen}, and <_{O_{F}} on R(F) := {M ∈ M | ⟨F, M⟩ ∈ Gen}. For ⟨F, M⟩ , ⟨F′, M′⟩ ∈ Gen we set:

1. F <_{O_{M}} F′ iff there is an γ with 1 ≤ γ < β such that c_{γ}(F, M) < c_{γ}(F′, M) and for all α < γ : c_{α}(F, M) = c_{α}(F′, M).

2. M <_{O_{F}} M′ iff there is an γ with 1 ≤ γ < β such that c_{γ}(F, M) < c_{γ}(F, M′) and for all α < γ : c_{α}(F, M) = c_{α}(F, M′).

Then, we can define ⪯_{F} as the inverse of <_{O_{F}}, and ⪯_{M} in the same way. If we assume furthermore that F and M are disjoint, and set ⪯= (⪯_{p})_{p∈P} for P = F or P = M, then ⟨F, M, Gen, ⪯⟩ is a one–sided Blutner structure.

It is easy to see that two one–sided Blutner structures B_{F} and B_{M}, where B_{F} is F–sided, and B_{M} is M–sided, generate a two–sided Blutner structure B = ⟨F, M, Gen, (⪯_{p})_{p∈P} ⟩ if we set P = P_{F} ∪ P_{M}. Hence, we see that any pair ⟨O_{1}, O_{2}⟩ with O_{i} = ⟨Gen, C_{i}⟩ generates a two–sided Blutner structure.

Now we also show the inverse. Again it is easy to see that we can separate a two–sided Blutner structure into a F–sided and a M–sided structure. Hence, we can restrict our considerations to one–sided structures. We show that we can find for any F–sided Blutner structure B = ⟨F, M, Gen, ⪯⟩ where the inverse of ⪯_{M} is a well–founded pre–order for all M ∈ M an underlying OT–system ⟨Gen, C_{F}⟩ which generates B.

Lemma 3.7 For every F–sided Blutner structure B = ⟨F, M, Gen, ⪯⟩ where the inverse ≤_{M} of ⪯_{M} is a well–founded pre–order for all M ∈ M there exists an OT–system ⟨Gen, C_{F}⟩, such that for all ⟨F, M⟩ , ⟨F′, M′⟩ ∈ Gen:

F ≤_{M} F′ ⟺ F ≤_{O_{F}} F′.

Proof: Let ≤_{M} be the inverse relation of ⪯_{M} on R(M). By assumption, ≤_{M} is well–founded. For each F ∈ R(M) we can define equivalence classes [F]_{M} := {F′ ∈ R(M) | F ≤_{M} F′ & F′ ≤_{M} F }, where [F]_{M} ≤_{M} [F′]_{M} ⇔ F ≤_{M} F′. Hence ⟨{[F]_{M} | F ∈ R(F)}, ≤_{M}⟩ is well–ordered for each M ∈ M. Let f(M, F) be the associated order type of [F]_{M}. Then we set:

c_{α}(M, F) := 0 ⟺ f(M, F) = α
c_{α}(M, F) := 1 ⟺ f(M, F) ≠ α.

We set O_{F} := ⟨Gen, C_{F}⟩ with C_{F} := ⟨c_{α}⟩_{α<β_{F}}, where β_{F} := sup_{M∈M}(β_{M} + 1), and β_{M} := sup_{F ∈R(M)}(f(M, F) + 1). Let F, F′ ∈ R(M), γ := f(M, F) and γ′ := f(M, F′). Then we find: F ≤_{M} F′ iff γ ≤ γ′ iff (∀α < β_{M} c_{α}(M, F) = c_{α}(M, F′)) ∨ ∀α < γ (c_{α}(M, F) = c_{α}(M, F′) ∧ c_{γ}(M, F) < c_{γ}(M, F′)) iff F ≤_{O_{F}} F′. □ The same result holds for M. Hence, we can sum up our result as:

Lemma 3.8 Let B = ⟨F, M, Gen, ⪯⟩ be a Blutner structure where the inverse of ⪯_{F} and ⪯_{M} are well–founded relations. Then there is a pair ⟨O_{F}, O_{M}⟩ of OT–systems O_{F} = ⟨Gen, C_{F}⟩ and O_{M} = ⟨Gen, C_{M}⟩ which generate B.

Blutner Structures with Context–Sensitive Constraints

Our structures represent cases where the constraints depend on arguments of the form ⟨F, M⟩. We want to extend Blutner structures in order to be able to handle arbitrary contexts given by a set C. In case of Mattausch’s Example we considered a constraint which says that the gender of a pronoun must agree with the sex of the person referred to. The real person is neither part of a natural sentence nor of its translation into a sentence of formal logic. Later, in Sections 4 and 5 we define structures where the real world and the information state of the interpreter are possible arguments for constraints. But we will show that Blutner structures with contexts C are not really new structures, i.e. that they can be considered to be Blutner structures in the sense of Def. 3.1.

Definition 3.9 (Blutner Structure with Contexts) A Blutner structure with contexts is a tuple B = ⟨F, M, C, Gen, ⪯⟩ where

• F and M are disjoint sets.

• C is a set.

• Gen is a subset of C × F × M.

• ⪯ is a family (⪯_{p})_{p∈P} with P ⊆ C × (F ∪ M) where

– ⪯_{c,F} is a linear pre–order on {M | ⟨c, F, M⟩ ∈ Gen}.

– ⪯_{c,M} is a linear pre–order on {F | ⟨c, F, M⟩ ∈ Gen}.

We call F a set of forms, M a set of meanings, and C a set of contexts.

We show that every Blutner structure B = ⟨F, M, C, Gen, ⪯⟩ with contexts can be represented as a Blutner structure in the sense of Definition 3.1.

Let ⟨F, M, C, Gen, ⪯⟩ be given. Then we set:

M′ := {⟨c, M⟩ | ∃F ∈ F ⟨c, F, M⟩ ∈ Gen},
F′ := {⟨c, F ⟩ | ∃M ∈ M ⟨c, F, M⟩ ∈ Gen},
Gen′ := {⟨⟨c, F ⟩ , ⟨c, M⟩⟩ | ⟨c, F, M⟩ ∈ Gen}.

Then we can define ⪯:

⟨c, M⟩ ⪯′_{⟨c,F ⟩} ⟨c, M′⟩ iff M ⪯_{c,F} M′
⟨c, F ⟩ ⪯′_{⟨c,M⟩} ⟨c, F′⟩ iff M ⪯_{c,M} M′.

⪯′_{⟨c,F ⟩} and ⪯′_{⟨c,M⟩} are linear pre–orders on the sets {⟨c, M⟩ | ⟨c, F, M⟩ ∈ Gen} and {⟨c, F ⟩ | ⟨c, F, M⟩ ∈ Gen} respectively. Hence, B′ = ⟨F′, M′, Gen′, ⪯′⟩ is a Blutner structure in the sense of Def. 3.1.

We now show that they both induce the same preference relation on Gen and Gen′. The map

e : Gen ⟶ Gen′, ⟨c, F, M⟩ ↦ ⟨⟨c, F ⟩ , ⟨c, M⟩⟩

is a bijection. Let ≤ be the pre–order on Gen induced by B, and ≤′ the pre–order on Gen′ induced by B′. Then, for all a, b ∈ Gen it holds that:

a ≤ b ⟺ e(a) ≤′ e(b).

This follows by:

⟨c, F, M⟩ ≤ ⟨c′, F′, M′⟩ ⇔

⇔ c = c′ & (M = M′ ∧ F ⪯_{c,M} F′ ∨ F = F′ ∧ M ⪯_{c,F} M′)
⇔ c = c′ & (M = M′ ∧ ⟨c, F ⟩ ⪯_{⟨c,M⟩} ⟨c, F′⟩ ∨ F = F′ ∧ ⟨c, M⟩ ⪯_{⟨c,F ⟩} ⟨c, M′⟩)
⇔ ⟨⟨c, F ⟩ , ⟨c, M⟩⟩ ≤′ ⟨⟨c′, F′⟩ , ⟨c′, M′⟩⟩

This allows us to generalise all results to Blutner structures with contexts.

4 Mattausch’s Example

In this section we show how to solve Mattausch’s Problem (2000) within a Bi-OT approach using Blutner structures. Beaver (2000) applied a version of a two–sided OT to predict choice and explain resolution of anaphoric expressions. Mattausch (2000) improves on this approach, and his discussion of bidirectional OT in the version of (Blutner, 2000), (Blutner, Jäger, 2000) or (Jäger, 2000) leads him to consider the following example (Mattausch, 2000, pp.33–36):

(3) Assume that Marion is a male person, and Jo a female one. The speaker wants to express with the second sentence that Jo was pulling Marion’s hair out.

a) Marion was frustrated with Jo. She was pulling his hair out.

b) Marion was frustrated with Jo. He was pulling her hair out.

c) Marion was frustrated with Jo. Jo was pulling Marion’s hair out.

The considered form–meaning pairs are

⟨F_{1}, M_{1}⟩ := ⟨She was pulling his hair out, pulling–hair–out(j, m)⟩

⟨F_{1}, M_{2}⟩ := ⟨She was pulling his hair out, pulling–hair–out(m, j)⟩

⟨F_{2}, M_{1}⟩ := ⟨He was pulling her hair out, pulling–hair–out(j, m)⟩

⟨F_{2}, M_{2}⟩ := ⟨He was pulling her hair out, pulling–hair–out(m, j)⟩

⟨F_{3}, M_{1}⟩ := ⟨Jo was pulling Marion’s hair out, pulling–hair–out(j, m)⟩

We need the following constraints: 1) Pronouns have to agree with the natural gender of the person referred to. 2) Pronouns are preferred over names. 3) Marion is interpreted by default as female, and Jo as male. 1) and 2) define preferences on forms, 3) on meanings. These constraints lead into the following circle:

In case of pulling–hair–out(j, m) ‘She was pulling his hair out’ is the preferred form over ‘He was pulling her hair out’.

In case of ‘She was pulling his hair out’ pulling–hair–out(m, j) is the preferred meaning over pulling–hair–out(j, m).

In case of pulling–hair–out(m, j) ‘He was pulling her hair out’ is the preferred form over ‘She was pulling his hair out’.

In case of ‘He was pulling her hair out’ pulling–hair–out(j, m) is the preferred meaning over pulling–hair–out(m, j).

This results into a circular structure:

⟨F_{3}, M_{1}⟩ ⟶ ⟨F_{1}, M_{1}⟩ ⟵ ⟨F_{2}, M_{1}⟩
↓  ↑
⟨F_{1}, M_{2}⟩ ⟶ ⟨F_{2}, M_{2}⟩

The situation where the speaker and hearer have to co–ordinate their choice of an optimal form–meaning pair is given by the context generated after the utterance of Marion was frustrated with Jo. The second sentence contains pronouns, hence, it is natural to seek for a dynamic framework to handle Mattausch’s Example. In a first step we will combine Dynamic Semantics with bidirectional OT using Blutner structures for (static) contexts. The underlying idea will be that Dynamic Semantics accounts for the meaning of formulas in a given context, and OT provides for the pragmatic constraints which govern anaphora resolution.

That OT should be seen in context with Dynamic Semantics has been suggested by Blutner (2000). The idea that the two theories should work together in anaphora resolution goes back to (Beaver, 2000), who was followed by Mattausch (2000).

Let L be a set of well–formed formulas of a first order language. We assume that for all sentences of natural language there are translations in L. Such a translation should be unique up to substitutions of free variables. We denote the set of all translations of a natural sentence F by F^{∗}. Let W be a set of models for L representing the possible states of affairs. Let W be a set of pairs (w, f) where f is a partial assignment function for variables and w ∈ W. We denote the set of variables by Var . In Dynamic Semantics it is common to identify the meaning of a sentence with its update potential, i.e. with a relation between world–assignment pairs. Hence, we assume that for every formula φ ∈ L [[φ]] there is a set of pairs ⟨σ, τ⟩ such that σ, τ ⊆ W. Furthermore, we assume that [[φ]] is a function. This means that the update effect of a sentence of natural language is given once we have resolved anaphora. This allows us to define the meaning [[φ]]_{σ} of a formula φ in context σ: It is defined if σ ∈ dom[[φ]], and [[φ]]_{σ} = τ ⇔ σ[[φ]]τ. The subsets σ, τ of W are called information states. They represent — and this is important for the following representation of contexts — the hearer’s knowledge.

The task for speaker and hearer in Mattausch’s Example is to find the correct resolution for and choice of the pronouns he/she and his/her in the environment ... was pulling ... hair out.

In general, the set of forms F for our Blutner structure is given by the set of all syntactically correct sentences of natural language. But for the present purpose we can restrict our considerations to the set:

F := \{\underbrace{She was pulling his hair out}_{F_{1}}, \underbrace{He was pulling her hair out}_{F_{2}}\}

The set M is the set of all possible translations:

M := {φ | φ ∈ L} = L

As the information of the hearer is represented by an information state σ ⊆ W, his choice of an optimal translation should be determined by this set, whereas the speaker should be able to rely for his choice of the best form on the true state of affairs as well. Hence, we consider contexts of the following form: c = ⟨w, σ⟩ where w represents the actual world, and σ ⊆ W the information state of the hearer, i.e.

C := {⟨w, σ⟩ | w ∈ W & w ∈ σ ⊆ W}.

Now we have to indicate which form–meaning pairs can be generated in which contexts. The elements in Gen have the form ⟨c, F, φ⟩, where c is a pair ⟨w, σ⟩. We have to consider the constraints imposed by our dynamic semantics and the fact that φ must be a possible translation for F. This leads to the following definition:

Gen := {⟨⟨w, σ⟩ , F, φ⟩ | φ ∈ F^{∗} & σ ∈ dom[[φ]] & ∃f (w, f) ∈ [[φ]]_{σ}}.

Gen is the set of all ⟨c, F, φ⟩ such that 1) φ is a possible translation for the natural sentence F, 2) the information state of the hearer can be updated with φ, and 3) the existential closure of φ must be a true sentence in w. dom[[φ]] denotes the domain of φ. Hence, if σ ∈ dom[[φ]], then [[φ]]_{σ} is defined. Gen is the set of all proper grammatical form–meaning pairs.

For pragmatic reasons this set would be too restrictive. This has to do with the limited perspectives of speaker and interpreter. In our example the hearer can rely for his interpretation in a context ⟨w, σ⟩ only on the information state σ. Hence, he has to consider all form–meaning pairs ⟨F, φ⟩ such that there is a context ⟨w′, σ⟩ where ⟨F, φ⟩ is properly grammatical. This means that the hearer’s set of alternatives is defined by:

Gen_{H} := {⟨⟨w, σ⟩ , F, φ⟩ | ∃w′ ∈ W ⟨⟨w′, σ⟩ , F, φ⟩ ∈ Gen}.

The speaker, on the other hand, has full knowledge about the utterance situation, i.e. the set of forms where his choice takes place is determined by the set Gen.

Of course this is not covered by our framework set up in the last section. It motivates the last modifications which we will provide following the discussion of Mattausch’s Example.

Now that we have set up the general framework we can consider Mattausch’s problem in more detail. We denote the object Marion by m, and Jo by j. As short forms we use:

φ(v_{1}, v_{2}) :⇔ pull–hair–out(v_{1}, v_{2}),
ψ(v_{1}, v_{2}) :⇔ Marion(v_{1}) ∧ Jo(v_{2}) ∧ frustrated–with(v_{1}, v_{2}).

We assume that the actual world is such that

w_{0} ⊧ ψ(m, j) ∧ φ(j, m) ∧ male(m) ∧ female(j)

We assume that the hearer chooses a variable x for Marion and a variable y for Jo when processing the sentence Marion was frustrated with Jo. His information state is then represented by the set

σ_{0} = {(w, f)|x, y ∈ domf &(w, f) ⊧ Marion(x)∧Jo(y)∧frustrated–with(x, y)}.

This implies that the hearer has to choose the variable x as a translation for a pronoun if it should refer to Marion, and y if it should refer to Jo. With (Mattausch, 2000) we do not assume that Marion(x) ⇒ female(x) or Jo(y) ⇒ male(y) forms part of the meaning of Marion and Jo. But we have to assume — and here we again follow Mattausch (2000) — that it is part of the default interpretation.

The context where the speaker has to choose the best form and where the hearer has to find the correct translation is given by the pair c = ⟨w_{0}, σ_{0}⟩.

The speaker wants the hearer to update his information state with:

τ_{1} := {(w, f) | x, y ∈ domf & f(x) = m & f(y) = j & (w, f) ⊧ φ(y, x)}.

This is the meaning of the formula φ(y, x) in σ_{0}, i.e. [[φ(y, x)]]_{σ_{0}} = σ_{0}∩τ_{1}. Now it is the assumption for Mattausch’s Example that the best choice for the speaker is a pronoun which agrees with the natural gender of the persons it is intended to refer to. Hence, he should choose He for Marion and She for Jo. This means that he prefers in context c = ⟨w_{0}, σ_{0}⟩ F_{1} over F_{2}, i.e. F_{2} ≺_{c,φ(y,x)} F_{1}.

Now we have to take the perspective of the interpreter and choose the best translation for F_{1}. We assume here that it is part of the semantics of a pronoun whether or not its referent is male or female. Of course, it may be more appropriate to call it a presupposition, but we don’t want to enter into the subtleties of presupposition theory. It follows that the set of translations for F_{1} is given by^{6}:

F_{1}^{∗} = \{\underbrace{φ(v_{1}, v_{2}) ∧ female(v_{1}) ∧ male(v_{2})}_{μ(v_{1},v_{2})} | v_{1}, v_{2} ∈ Var\}

The set of alternatives where the choice takes place in context c = ⟨w_{0}, σ_{0}⟩ is defined as:

R_{c}(F_{1}) = {λ ∈ L | ∃w ∈ W ⟨⟨w, σ_{0}⟩ , F_{1}, λ⟩ ∈ Gen_{H}}

Hence, R_{c}(F_{1}) = {μ(v_{1}, v_{2}) | v_{1}, v_{2} ∈ Var & σ_{0} ∈ dom[[μ(v_{1}, v_{2})]] & ∃w∃f (w, f) ∈ [[μ(v_{1}, v_{2})]]_{σ_{0}}} = {μ(v_{1}, v_{2}) | (v_{1} = x ∧ v_{2} = y) ∨ (v_{1} = y ∧ v_{2} = x)} = {μ(x, y), μ(y, x)}. Here we have to assume that x and y are the only variables interpreted so far by the hearer.

We impose the same constraints as Mattausch for the choice of optimal meanings. Hence, we have to assume that the hearer prefers default interpretations over non–default interpretations. But this means that he has to choose y for He and x for She because σ_{0} ⊧ Jo(y) & Marion(x). Hence, he will translate F_{1} into μ(x, y), and update his information state with the set:

τ_{2} := {(w, f) | x, y ∈ domf & (w, f) ⊧ φ(x, y) ∧ female(x) ∧ male(y)}.

Now we have to switch to the perspective of the speaker again. He has to choose the optimal sentence in the context c = ⟨w_{0}, σ_{0}⟩ for μ(x, y). Hence, in accordance with Definition 3.9 he has to choose the preferred form from the set

R_{c}(μ(x, y)) = {F ∈ {F_{1}, F_{2}} | ⟨c, F, μ(x, y)⟩ ∈ Gen}.

This is the set of all F ∈ {F_{1}, F_{2}} such that

μ(x, y) ∈ F^{∗} & σ_{0} ∈ dom[[μ(x, y)]] & ∃f (w_{0}, f) ∈ [[μ(x, y)]]_{σ_{0}}.

[[μ(x, y)]]_{σ_{0}} is the set of all (w, f) ∈ σ_{0} such that:

x, y ∈ domf & (w, f) ⊧ φ(x, y) ∧ female(x) ∧ male(y).

Hence, it is the set of all (w, f) where x, y ∈ domf, and where in (w, f) holds:

Marion(x) ∧ Jo(y) ∧ ψ(x, y) ∧ φ(x, y) ∧ female(x) ∧ male(y).

6Of course, our decision to make the gender of a pronoun part of the meaning, and therefore of its translation, has some repercussions on our previous definitions because now F_{1} is no more a possible choice for the producer. This follows because φ(y, x) is not a translation for F_{1}, hence ⟨⟨w_{0}, σ_{0}⟩ , F_{1}, φ(y, x)⟩ ∉ Gen. This problem is due to the strong condition for grammaticality which implies that the formula has to be an exact translation. But we can weaken this condition: The exact translation has to imply the formula. This is without influence on our subsequent discussion. The definition of Gen then is as follows: ⟨⟨w, σ⟩ , F, φ⟩ ∈ Gen iff

σ ∈ dom[[φ]] ∧ w ∈ [[φ]]_{σ} ∧ ∃ψ ∈ F^{∗} (σ ∈ dom[[ψ]] ∧ w ∈ [[ψ]]_{σ} ∧ [[ψ]]_{σ} ⊆ [[φ]]_{σ}).

But for all (w_{0}, f) with x, y ∈ domf and f(x) = Marion and f(y) = Jo it holds that (w_{0}, f) ⊧ ¬φ(x, y) ∧ ¬female(x) ∧ ¬male(y). Hence

R_{c}(μ(x, y)) = ∅.

I.e. in this context the speaker can find no grammatical sentence to choose. This implies that ⟨⟨w_{0}, σ_{0}⟩ , F_{1}, μ(x, y)⟩ is optimal in Gen_{H}. But the last result also shows that it is not an element of Gen. Intuitively, ⟨F_{1}, μ(x, y)⟩ should not be counted as an optimal form–meaning pair in context ⟨w_{0}, σ_{0}⟩. Of course, our considerations suggest that this is due to the fact that this pair is an element of Gen_{H} \ Gen, i.e. because it can’t be generated by our grammar for this context. If we restrict the search for optimal pairs to Gen, then we face the problem that ⟨F_{1}, μ(y, x)⟩ would be optimal. But this is neither an intuitive nor reasonable solution as clearly the hearer should translate F_{1} as μ(x, y). Hence, we postulate the following principle:

We call the elements of Gen_{H} \ Gen dead ends, and require for optimality that the considered form–meaning pair is maximal in Gen and that it has no dead ends as successors in Gen_{H}.

Don’t force the interpreter to choose an ungrammatical meaning! The principle can also be incorporated into the notion of weak optimality.

We first show how the Mattausch problem can be solved with this principle, and then we supply a precise description of the necessary modifications to Blutner structures.

According to our definition, the pair ⟨She was pulling his hair out, μ(x, y)⟩ is a dead end in context c = ⟨w_{0}, σ_{0}⟩. Hence, the triple ⟨c, F_{1}, μ(y, x)⟩ is a maximal element in Gen but it should not be counted as optimal because μ(y, x) ≺_{c,F_{1}} μ(x, y) and ⟨c, F_{1}, μ(x, y)⟩ ∉ Gen. The principle stated above implies that we have to exclude all elements in Gen which necessarily lead into a dead end, i.e. we have to remove all triples of the form ⟨c, F_{1}, . ⟩. In this way we reduce the set of possible choices for the speaker, and we get new optimal form–meaning pairs. Especially, F_{1} is no longer a possible choice. We now consider Mattausch’s problem in its full version with originally three choices for the speaker, i.e. with F := {F_{1}, F_{2}, F_{3}} where

F_{1} := She was pulling his hair out,

F_{2} := He was pulling her hair out,

F_{3} := Jo was pulling Marion’s hair out.

Our considerations show that the choice of F_{1} for φ(y, x) in situation ⟨w_{0}, σ_{0}⟩ leads necessarily into a dead end, hence our mechanism removes it from F. F_{2} is neither a possible choice because ⟨⟨w_{0}, σ_{0}⟩ , F_{2}, φ(y, x)⟩ is not an element of Gen. Hence, it remains only F_{3} as a possible choice. Of course, ⟨⟨w_{0}, σ_{0}⟩ , F_{3}, φ(y, x)⟩ is grammatical, and it is easy to see that φ(y, x) is also the preferred translation for F_{3} for the interpreter. Hence, it turns out that

⟨⟨w_{0}, σ_{0}⟩ , Jo was pulling Marion’s hair out, pull–hair–out(y, x)⟩

is optimal.

The following picture provides a graphical solution for Mattausch’s Problem. The first row lists the different forms the speaker can choose. In the first column we list the different contexts. In fact, we list only the world w of the pair ⟨w, σ⟩ because σ is in all four cases the same set, namely σ_{0} = {w_{0}, w_{1}, w_{2}, w_{3}}. All four situations are indiscernible for the interpreter, indicated by the dashed box around the worlds. In the second column we list the different formulas which represent the possible translations for the forms. We use the following abbreviations:

φ(v_{1}, v_{2}) iff pull–hair–out(v_{1}, v_{2}),
μ(v_{1}, v_{2}) iff φ(v_{1}, v_{2}) & female(v_{1}) & male(v_{2}),
λ(v_{1}, v_{2}) iff φ(v_{1}, v_{2}) & male(v_{1}) & female(v_{2}).

The worlds w_{i} are those worlds where Marion(x) ∧ Jo(y) ∧ frustrated–with(x, y), and where the formulas listed in the second column hold.

[figure: λ(x, y); φ(x, y); λ(y, x); φ(y, x); μ(x, y); φ(x, y); μ(y, x); φ(y, x); w_{0}; w_{1}; w_{2}; w_{3}; Jo/Ma; She/his; He/her; Ma/Jo; Dead End; Dead End]

The big dots represent the form–meaning pairs which can be generated in the context listed in the first column. The horizontal arrows show the preferences of the speaker, the vertical ones the preferences of the interpreter. The vertical arrows which cross the lines separating the different contexts indicate that they lead to a dead end. Of course, the dead ends itself are not listed in the picture. The circles around the big dots indicate the optimal form–meaning pairs.

5 Bidirectional OT for Dynamic Contexts

It remains to describe the structures which we used to solve Mattausch’s Problem in more detail. First we notice that it was essential that the set of meanings where the interpreter can choose the best meaning may depend on a different set Gen_{H} of possible form–meaning pairs than the speaker’s choice. Of course, this set is generated by an equivalence relation on contexts. This has also some consequences for the preference relation on meanings and forms: The preference relation on forms which determines the speaker’s choice is defined for the original contexts, whereas the interpreter’s preference relation on meanings is defined for equivalence classes of contexts.

We have seen in Section 3 that we can identify a Blutner structure with a pair of OT–systems ⟨O_{F}, O_{M}⟩, or equivalently with a pair ⟨B_{F}, B_{M}⟩ of two one–sided Blutner structures. Both systems are built over the same set of grammatical form–meaning pairs Gen. We use this representation and generalise it in order to cover dynamic contexts.

Definition 5.1 (Blutner Structures for Dynamic Contexts) Let ⟨B_{F}, B_{M}, [ ]⟩ be a triple where

1. B_{F} = ⟨F, M, C, Gen, ⪯⟩ is a F–sided Blutner structure.

2. B_{M} = ⟨F, M, C_{H}, Gen_{H}, ⪯⟩ is a M–sided Blutner structure.

3. [ ] : C ⟶ C_{H}, c ↦ [c], maps C onto C_{H}.

4. Gen_{H} = {⟨[c], F, M⟩ | ⟨c, F, M⟩ ∈ Gen}

We write c′ ∈ [c] iff [c′] = [c].

As [ ] is a function, it follows that c ∼ c′ ⇔ [c] = [c′] defines an equivalence relation. This definition is slightly more general than is needed for dynamic contexts. There, contexts had the form ⟨w, σ⟩, where w represents the real utterance situation, and σ the common ground. If we set [⟨w, σ⟩] := {⟨v, σ⟩ |v ∈ σ}, or simply [⟨w, σ⟩] := σ, then Gen_{H} is of the form:

Gen_{H} = {⟨[⟨w, σ⟩], F, φ⟩ | ⟨⟨w, σ⟩ , F, φ⟩ ∈ Gen}.

Hence, for a fixed F ∈ NL we find that the set of meanings R_{[⟨w,σ⟩]}(F) where the interpreter can make his choice is given by:

R_{[⟨w,σ⟩]}(F) = {φ ∈ L | ⟨[⟨w, σ⟩], F, φ⟩ ∈ Gen_{H}}
= {φ ∈ L | ∃v ∈ σ ⟨⟨v, σ⟩ , F, φ⟩ ∈ Gen}.

This means that he has to consider a formula φ as a translation for a sentence F, iff there is any epistemically possible context for him where ⟨F, φ⟩ is grammatical. This is exactly as intended.

A two–sided Blutner structure for dynamic contexts again induces a pre– order ≤ on Gen:

Definition 5.2 Let B = ⟨F, M, Gen, ⪯⟩ be a F–sided Blutner structure, and let ⟨B_{F}, B_{M}, [ ]⟩ be a Blutner structure for dynamic contexts. Then we define a pre–order ≤ on Gen × Gen by: ⟨c, F, M⟩ ≤ ⟨c′, F′, M′⟩ iff

(c = c′ & M = M′ & F ⪯_{c,M} F′) ∨ (c′ ∈ [c] & F = F′ & M ⪯_{[c],F} M′).

Let us assume for now that the sets of forms and meanings are finite, and that the preference relations ⪯ are proper linear orders. If we assume furthermore that the induced order ≤ on Gen is well–founded, then it is known that there exists an algorithm which leads necessarily to an optimal form–meaning pair. The idea goes back to (Blutner, 1998) and (Blutner, 2000), and is discussed in more detail in (Jäger, 2000). The algorithm starts with some meaning M_{1}, then the speaker chooses the most preferred form F_{1}. Then the interpreter chooses his most preferred meaning M_{2} for F_{1}, and then the speaker again chooses a form F_{2} for M_{2}. This defines a sequence (a_{n})_{n∈N} of forms and meanings where a_{2n} ∈ M and a_{2n+1} ∈ F. If ⟨≤, Gen⟩ is generated by an OT–system, Jäger (2000) has shown that this sequence ultimately chooses always the same forms and meanings. Of course, this holds as long as ⟨≤, Gen⟩ is well–founded. If ⟨≤, Gen⟩ is generated by a Blutner structure B then this sequence becomes a circle, i.e. there exist M, N ∈ N such that for all m ≥ M and for all k ∈ N a_{m+k·N} = a_{m}. But it may happen that it does not always choose the same forms and meanings, i.e. that a_{m+2} ≠ a_{m}. Now, if we consider Blutner structures for dynamic contexts, then a third case can occur: the sequence can run into a dead end, i.e. it may happen that the interpreter chooses a meaning M such that there is no F for the speaker to choose. Hence, it may happen that there is an m ∈ N such that the sequence can not be extended beyond a_{m}. Exactly this happens if the interpreter prefers in context c a meaning M for which there is no grammatical triple ⟨c, F, M⟩ ∈ Gen.

Definition 5.3 (Dead Ends) Let B_{F} = ⟨F, M, Gen, ⪯⟩ be a F–Blutner structure, and let ⟨B_{F}, B_{M}, [ ]⟩ be a Blutner structure for dynamic contexts. Dead ends are a set of ungrammatical form–meaning pairs for a certain context:

DE := {⟨c, F, M⟩ | ⟨[c], F, M⟩ ∈ Gen_{H} & ⟨c, F, M⟩ ∉ Gen}

A form–meaning pair leads into a dead end if it is an element of DE^{+}, where DE^{+} is the set of all ⟨c, F, M⟩ ∈ Gen:

∃M′ : M ≺_{[c],F} M′ & ∀M′′(M′ ⪯_{[c],F} M′′ ⇒ ⟨c, F, M′′⟩ ∈ DE).

Definition 5.4 (Optimality) Let ⟨B_{F}, B_{M}, [ ]⟩ be a Blutner structure for dynamic contexts. Let ⟨≤, Gen⟩ be the induced order. We call an element ⟨c, F, M⟩ ∈ Gen optimal for ⟨B_{F}, B_{M}, [ ]⟩, iff it is maximal in ⟨≤, Gen \ DE^{+}⟩.

Now we can specify how the preferences of speaker and interpreter enter into the resolution problem of pronouns, and therefore how it determines the information update.

The resolution problem was created by an (underspecified) translation operation ^{∗} which maps a sentence of natural language onto a subset of the sentences of a formal language L, and by a dynamic semantic for L. Hence, we can single out three structures which determine the optimal choice of pronouns and their translation:

⟨NL, L,^{∗} ⟩ where ^{∗} : NL ⟶ P(L) correlates natural sentences and formal sentences. The translation part.

⟨L, W, [[ ]]⟩ where W is a set of world–assignment pairs, and where [[ ]] is a function from L into sets of pairs ⟨σ, τ⟩ of subsets of W. The dynamic semantic part.

⟨B_{F}, B_{M}, [ ]⟩ the Blutner structure with contexts C = {⟨w, σ⟩ | w ∈ σ ⊆ W}. The Blutner structure is determined by ⟨NL, L,^{∗} ⟩ and ⟨L, W, [[ ]]⟩ up to preferences, i.e. F = NL, M = L, and

Gen := {⟨⟨w, σ⟩ , F, φ⟩ | φ ∈ F^{∗} & σ ∈ dom[[φ]] & ∃f (w, f) ∈ [[φ]]_{σ}}.

Together they define a transition system ⟨C, NL, ⟶⟩ such that for all c = ⟨w, σ⟩ , c′ = ⟨w′, σ′⟩ ∈ C:

c ⟶^{F} c′ ⟺ w = w′ & ∃φ ∈ L (⟨c, F, φ⟩ is optimal ∧ σ′ = [[φ]]_{σ}).

Now, if we assume that the preferences induced by the OT–constraints are linear orders (not only pre–orders), then there can be only one φ such that ⟨c, F, φ⟩ is optimal. Hence, we can derive for a fixed world w a dynamic semantics for NL: ⟨W, NL, [[ ]]⟩ with

σ[[F]]τ ⟺ ⟨w, σ⟩ ⟶^{F} ⟨w, τ⟩ .

6 Conclusion

The aim of our paper was to outline a framework which allows to combine bidirectional OT and Dynamic Semantics. We introduced Blutner structures which improve over OT–systems. Blutner structures are generated by two OT– systems, one for the speaker and one for the interpreter. They allow

• to generate circular preferences on form–meaning pairs,

• to consider arbitrary context–sensitive constraints,

• to explain the role of the interlocutors’ different epistemic perspectives in dynamic contexts.

Our model for Mattausch’s Example shows that the circularity is only apparent. If we take utterance context and epistemic context into account, then the circularity vanishes. But this is an empirical finding, no longer a restriction imposed a priori by the underlying OT–structure. The consideration of the role of epistemic perspectives leads us to postulate an additional restriction on the set of form–meaning pairs which can count as optimal choices. As the interpreter has only limited information about the utterance context he may prefer a meaning M for a form F such that ⟨F, M⟩ is not grammatical in the given context. We called such a pair a dead end. We claimed that only those form–meaning pairs can count as optimal which don’t lead into a dead end, i.e. the speaker is not allowed to choose a form which misleads the interpreter.

References

D. Beaver (2000): The Optimization of Discourse; ms, Stanford.

R. Blutner (1998): Lexical Pragmatics; Journal of Semantics 15, pp. 115–162.

R. Blutner (2000): Some Aspects of Optimality in Natural Language Interpretation; to appear in Journal of Semantics.

R. Blutner, G. Jäger (2000): Against Lexical Decomposition in Syntax; to appear in A.Z. Wyner (ed.): Proceedings of IATL 15, University of Haifa.

G. Jäger (September 2000): Some Notes on the Formal Properties of Bidirectional Optimality Theory; ms, ZAS Berlin.

J. Mattausch (November 2000): On Optimization in Discourse Generation; master thesis, Universiteit van Amsterdam.

H. Zeevat (2000): Semantics and Optimality Theory; H. de Hoop, H. de Swart (eds.): Optimality Theoretic Semantics, OTS preprint, University of Utrecht.

Contents

1 Introduction 1 2 OT–Systems 3 3 Blutner Structures 7 4 Mattausch’s Example 12 5 Bidirectional OT for Dynamic Contexts 18 6 Conclusion 21