\underline{\underline{\underline{6}}} Ambiguity under changing contexts

Abstract. Notions of disambiguation supporting a compositional interpretation of ambiguous expressions and reflecting intuitions about how sentences combine in discourse are investigated. Expressions are analyzed both inductively by breaking them apart, and co-inductively by embedding them within larger contexts.

1. Introduction

It is not clear how to distinguish ambiguous from unambiguous expressions without appealing to some process of disambiguation that both separates and links them. Nor is it clear why one would bother with expressions — be they ambiguous or not — if they effected no change in context (typically identified, for simplicity and concreteness, with the “common ground”). Insofar as disambiguation is one of the effects that asserting an expression can have, it is natural to study ambiguity within (so-called) “dynamic semantics” (e.g., Heim [10] and Kamp and Reyle [12]), central to which is a binary “merge” operation ^{∧} on formulas φ and ψ such that φ^{∧}ψ represents the context obtained by asserting the second argument ψ at a(n initial) context represented by φ.^{1} The present paper is an attempt to provide an analysis of expressions given at the level of sentences (or formulas) and sequences of sentences (i.e., discourse), respecting the two aforementioned intuitions,

Ambiguity as incomplete interpretation: ambiguous expressions require disambiguation for an unambiguous interpretation

and Semantics as change: the meaning of a formula is the change in context it induces.

The aim is to develop these intuitions in accordance with the principle of compositionality (viz., the meaning of a whole is a function of the meaning of its parts) and with a view to reasoning with partial disambiguations.

1.1. Outline of the paper. Towards that end, various notions of disambiguation are considered below. The simplest, introduced in §2.1, is a binary relation on expressions that picks out an unambiguous formula for an ambiguous expression assembled from unambiguous ones through a binary logical connective •. (The idea is to analyze an expression e that is ambiguous between two unambiguous formulas φ and φ′ as φ • φ′, rather than say, the unambiguous disjunction φ ∨ φ′.) More generally, a disambiguation can be viewed as a mapping from an ambiguous expression to an unambiguous one. This notion is employed in §2.2 to extend a relation of logical consequence between unambiguous formulas to ambiguous expressions. All this presupposes, however, a unique choice of a disambiguation, whereas ambiguity arises (in practice) precisely when identifying the appropriate disambiguation (for a particular context) is problematic. Still, in introducing a notion of disambiguation, we have made some progress; to address ambiguity, our analyses of • and of ambiguous consequence relations need only be lifted from a single disambiguation to a family of disambiguations (say, through quantification). A family of disambiguations may, in turn, be viewed as a partial disambiguation, the semantics for which §2.3 begins to explore.

1The notation ^{∧} is meant to suggest a conjunction ∧ lifted (!) to a dynamic setting, which — contrary to what the alternative notation + (adopted by some) might imply — need not be commutative any more so than string concatenation.

For a compositional semantic interpretation of ambiguous expressions, it turns out to be useful to build into the notion of a disambiguation a specification not only of what unambiguous formulas an expression can be reduced to, but also of how — say, by merging with other expressions — that proceeds. Accordingly, disambiguations are characterized in §3 (the main section of the present paper) as incremental processes, stretching forward and backward in time. Finally, §4 discusses how the various pictures of disambiguation complement each other and fit within dynamic semantics.

1.2. A few examples (for orientation). As the sequel is fairly abstract, some examples might be useful to keep in mind. Suppose the sentence

 (A1)  Josef loves squash

has exactly two unambiguous interpretations, given by

 (U1)  Josef loves the sport of squash

and

 (U2)  Josef loves the vegetable squash.

(For the sake of the argument, let us take the words Josef and loves to be unambiguous — implausible though that may be.) A “cooperative” speaker who utters (A1) is assumed to mean either (U1) or (U2), but not (U1) ∨ (U2). §2 below analyzes (A1) as (U1) • (U2), a formal (unambiguous) interpretation of which requires a choice — i.e., a disambiguation — between (U1) and (U2). Just what disambiguation is appropriate may be clear from the context. For instance, the choice (U1) is natural if the utterance of (A1) is preceded by

 (U3)  Many people are fond of indoor sports.

That is, (U1), as opposed to (U2), can be said to be a consequence of the discourse

 (A2)  Many people are fond of indoor sports.
               Josef loves squash.

The proper disambiguation may also become evident further on in the discourse. In particular, (A1) presumably means (U2) within the two-sentence discourse formed by following (A1) up with

 (A3)  He eats it raw.

Moreover, in this case the disambiguation is mutual; (A1) also disambiguates the pronouns he and it in (A3). This gives rise to the complication involving acyclicity mentioned in §3, and, in addition, motivates an underspecified representation of ambiguity. In isolation, (A3) is infinitely ambiguous inasmuch as the pronouns he and it might mean any number of things. Rather than constructing (A3) from an infinitary version of •, it is simpler to treat (A3) as an underspecified representation in its own right, alongside expressions such as (U1) • (U2). Finally, observe that ambiguities may stay unresolved indefinitely

 (A4)  . . . Different things appeal to different
               people.  Josef loves squash.  Simone
               can't stand it. . . .

2. The necessity of contextual disambiguation

Let Φ be a set of formulas that are unambiguous insofar as each φ ∈ Φ has a well-defined semantic interpretation [[φ]]. Suppose e is an expression that intuitively is ambiguous between two formulas φ and φ′ in Φ. Perhaps the most simple-minded way of analyzing e is to equate it with the disjunction φ ∨ φ′, under the assumption that there is a fixed binary operation F_{∨} (such as set union) relative to which φ_{1} ∨ φ_{2} is to be interpreted as F_{∨}([[φ_{1}]], [[φ_{2}]]), for all φ_{1} and φ_{2} ∈ Φ. But then where in this picture does disambiguating information enter? If the interpretation of φ∨φ′ is determined unambiguously by the interpretations [[φ]] and [[φ′]] of the disjuncts φ and φ′ respectively, then does reducing e to φ ∨ φ′ not abstract away the ambiguity in e? It is plausible enough that ambiguous expressions must somehow be converted into unambiguous formulas. What is disturbing about this disjunctive analysis, however, is that it carries out the conversion, without calling for any disambiguating information. This objection applies (as pointed out by an anonymous referee) to any fixed (unambiguous) combination of φ and φ′, not just disjunction. Disjunction has attracted, however, by far the greatest attention (and criticism) in the literature (see, for example, van Deemter [4], Poesio [14] and other articles in that volume), suggesting consequence relations between ambiguous expressions that will (among other things) be considered in this section.

2.1. Choosing between unambiguous formulas. Bringing disambiguations into the picture, consider a binary logical connective •, interpreted relative to a binary relation ≺ on formulas that chooses between its arguments φ and φ′ according say, to^{2}

(1)  [[φ • φ′]]_{≺} = \{ \begin{matrix}[[φ]] & if φ ≺ φ′ \\ [[φ′]] & otherwise. \end{matrix}

2A similar “meta-or” connective is proposed in p.234 of van Deemter [4], the novelty of the present approach being to make the disambiguation ≺ explicit.

The plain intuition in (1) is that φ ≺ φ′ means: choose φ over φ′. In the sense that (1) forces a choice between [[φ]] and [[φ′]], the relations ≺ appropriate for (1) represent total disambiguations. We will consider partial disambiguations shortly, but it will prove instructive to first look carefully at (1), and to formulate it more generally as follows.

Definition 1. Let Φ^{•} be the set of expressions obtained from Φ by adding a closure condition for • to those for Φ. Given a binary relation ≺ on Φ^{•}, define the function ·_{≺} : Φ^{•} → Φ inductively by

φ_{≺} = φ for φ ∈ Φ
(2)  (e • e′)_{≺} = \{ \begin{matrix}e_{≺} & if e ≺ e′ \\ e′_{≺} & otherwise \end{matrix}
γ(e, …, e′)_{≺} = γ(e_{≺}, …, e′_{≺}) for each connective γ in Φ .

Given Definition 1, a function [[·]] interpreting Φ can be extended to a function [[·]]_{≺} interpreting Φ^{•} by composing ·_{≺} with [[·]],

for every e ∈ Φ^{•}, [[e]]_{≺} = [[e_{≺}]] ,

thereby generalizing line (1) smoothly to

[[e • e′]]_{≺} = \{ \begin{matrix}[[e]]_{≺} & if e ≺ e′ \\ [[e′]]_{≺} & otherwise \end{matrix}

for all e and e′ ∈ Φ^{•} (and similarly for other logical connectives such as ∨, [[e ∨ e′]]_{≺} = F_{∨}([[e]]_{≺}, [[e′]]_{≺})). Now, to isolate the essential contribution that ≺ makes to [[·]]_{≺}, define the binary relation ≺^{•} on Φ^{•} by

e ≺^{•} e′ iff [[e]]_{≺} ≠ [[e′]]_{≺} and [[e • e′]]_{≺} = [[e]]_{≺}

for all e, e′ ∈ Φ^{•}. It is a routine matter to prove

Proposition 1. Let ≺ and ≺′ be binary relations on Φ^{•}. Then (i) [[·]]_{≺} = [[·]]_{≺^{•}} (ii) [[·]]_{≺} = [[·]]_{≺′} iff ≺^{•}= ≺′^{•} (iii) ≺^{•} is an irreflexive relation contained in ≺ and (iv) if

(3)  [[e • e′]]_{≺} = [[e′ • e]]_{≺}

holds for all e and e′ ∈ Φ^{•}, then ≺^{•} is asymmetric (i.e., e ≺^{•} e′ implies not e′ ≺^{•} e).

Note that the commutative principle (3) is faithful to the intuition underlying (1) that ≺ specifies a choice between φ and φ′ to disambiguate the expression φ • φ′. Faithful too is the associative principle

(4)  [[(e • e′) • e′′]]_{≺} = [[e • (e′ • e′′)]]_{≺}

which holds for every transitive relation ≺. Unfortunately, (4) does not seem sufficient to guarantee that ≺^{•} is transitive; it is easy enough to see that e ≺^{•} e′ and e′ ≺^{•} e′′ imply, in the presence of (4), that [[e • e′′]]_{≺} = [[e]]_{≺}; but what is lacking to conclude e ≺^{•} e′′ is that [[e]]_{≺} ≠ [[e′′]]_{≺}. Accordingly, let us define (given ≺) a slightly different relation ⪯^{•} on Φ^{•} by

e ⪯^{•} e′ iff [[e • e′]]_{≺} = [[e]]_{≺}

for all e, e′ ∈ Φ^{•}.

Proposition 2. Let ≺ and ≺′ be binary relations on Φ^{•}. Then (i) [[·]]_{≺} = [[·]]_{⪯^{•}} (ii) [[·]]_{≺} = [[·]]_{≺′} iff ⪯^{•}= ⪯′^{•} (iii) ⪯^{•} is a reflexive relation contained in ≺ ∪ {(e, e′) ∈ Φ^{•} × Φ^{•} : [[e]]_{≺} =

[[e′]]_{≺}}. (iv) if (3) holds then

e ⪯^{•} e′ and e′ ⪯^{•} e imply [[e]]_{≺} = [[e′]]_{≺}

and

(v) if (4) holds for all e, e′ and e′′ ∈ Φ^{•}, then ⪯^{•} is transitive. The modifications in Proposition 2 to parts (iii) and (iv) of Proposition 1 are somewhat minor. What is perhaps more troubling is that missing from Proposition 2 is an assertion stating the existence of a relation ≤ on the range of [[·]] such that

(5)  ⪯^{•} = {(e, e′) ∈ Φ^{•} × Φ^{•} : [[e]]_{≺} ≤ [[e′]]_{≺}}

(or, in Proposition 1, some relation < similarly characterizing ≺^{•}). Further conditions on ≺ need to be made in order to guarantee the existence of a relation ≤ satisfying (5). This matter will be taken up in §2.3, but for now note that (5) is, in general, implausible, given line (2). Indeed, the syntactic and total character of disambiguation in (2) suggests that it is natural to assume that ≺ is a linear order on Φ^{•} (inasmuch as the linearity of ≺ corresponds to the totality of disambiguation). Such an assumption can, under (3) and (4), be made without loss of generality, since an arbitrary binary relation ≺ satisfying (3) and (4) can be turned into a linear order inducing the same interpretation [[·]]_{≺}, by linearizing ⪯^{•}. Conversely, a linear order ≺ validates (3) and (4), whereas (3) fails for a (non-linear) partial order that contains neither (φ, φ′) nor (φ′, φ), for some φ and φ′ ∈ Φ such that [[φ]] ≠ [[φ′]].

Whether or not we agree that the “natural” relations ≺ relative to which (1) interprets • are linear orders, the crucial point is that • requires some binary relation ≺ for its interpretation, whereas an unambiguous connective such as ∨ does not (except possibly in interpreting disjuncts constructed with •). To see why this is so “crucial,” let us consider how entailment might be defined between ambiguous expressions.

2.2. A generalization and some consequences. Suppose the set Φ of unambiguous formulas is equipped with a binary relation |− on Φ of logical consequence. (E.g., φ |− φ′ iff [[φ ∨ φ′]] = [[φ′]].) A natural question to ask is how to lift |− to some set E ⊃ Φ of possibly ambiguous expressions. (E.g., E = Φ^{•}, although this identification is not necessary.) A number of proposals in the literature (e.g., van Deemter [4], Reyle [15]) are based on a function δ̂: E → Pow(Φ) specifying the set δ̂(e) of unambiguous formulas to which an expression e can be disambiguated. (E.g., δ̂(φ • φ′) = {φ, φ′}.) The relation |− can then be extended to E relative to a choice of quantifiers Q, Q′ ∈ {∀, ∃} by stipulating

(6)  e |−_{QQ′} e′ iff (Qφ ∈ δ̂(e))(Q′φ′ ∈ δ̂(e′)) φ |− φ′

for all e, e′ ∈ E. In particular, the relation |−_{∀∃} arises from a disjunctive analysis of an expression e as ⋁ δ̂(e)

⋁ δ̂(e) |− ⋁ δ̂(e′) iff (∀φ ∈ δ̂(e))(∃φ′ ∈ δ̂(e′)) φ |− φ′ .

As noted in van Deemter [4] (p. 207), the schemes |−_{QQ′} carry none of the “connections between interpretive choices” argued (also in Reyle [16]) to be essential to disambiguation — by which is meant that in (6), the choice of φ ∈ δ̂(e) need not constrain the choice of φ′ ∈ δ̂(e′) in the following sense. Recalling Definition 1 from §2.1, we might (instead) extend |− to Φ^{•} relative to a binary relation ≺ by stipulating that for all e, e′ ∈ Φ^{•},

e |−^{≺} e′ iff e_{≺} |− e′_{≺} ,

where, in contrast to (6), the choices e_{≺} ∈ δ̂(e) and e′_{≺} ∈ δ̂(e′) are “connected” by ≺. Now, it is true enough that |−^{≺} is hardly an alternative to |−_{∀∃} since (the choice of a particular) ≺ resolves away ambiguity. On the other hand, ambiguity can easily be re-introduced by collecting together a family O of relations ≺ and eliminating the dependence on a particular ≺ as follows. For all e, e′ ∈ Φ^{•}, form the set

{≺ ∈ O : e |−^{≺} e′}

and check if that set is a sufficiently large subset of O. Just what counts as “sufficiently large” depends on how loose or strict we want our ambiguous consequence relation to be. More precisely, the idea is to collect these sufficiently large sets in a family q of subsets of O, and to extend |− to Φ^{•} relative to q by defining

(7)  e |−^{q} e′ iff {≺ ∈ O : e |−^{≺} e′} ∈ q

for all e, e′ ∈ Φ^{•}. The difference between (6) and (7) is not only that the “interpretive choices” of the antecedent e and succedent e′ are “connected” in (7) by ≺, but also that Q and Q′ in |−_{QQ′} have been absorbed into one parameter q in |−^{q}. Is there a way of deriving the relations |−_{QQ′} (for whatever they are worth) using (7)? The answer is yes, provided we generalize our notion of disambiguations ≺ to make them dependent on context.

The notion of context dependence involved here can, in fact, be motivated by the discourse (A2) in §1.2, the point being that

(∗) within (A2), (U3) provides a context for which the natural reading of (U1) • (U2) is (U1).

To formalize (∗), let us choose the binary relation interpreting • according to the relevant context φ. Writing ≺^{φ} for that relation, (∗) can then be encoded by stipulating

(U1) ≺^{(U3)} (U2) .

More generally, without assuming that E = Φ^{•}, consider a function δ : (Φ × E) → Φ supporting the intuition that for every φ ∈ Φ and every e ∈ E,

δ(φ, e) ≈ an unambiguous formula to which e can

be disambiguated, given the “context” φ ,

so that, in particular, for every φ′ ∈ Φ,

δ(φ, φ′) = φ′ .

For the specific case of E = Φ^{•}, such a function δ might (recalling Definition 1) be given by

(8)  δ(φ, e) = e_{≺^{φ}}

for an appropriate function mapping formulas φ ∈ Φ to binary relations ≺^{φ} on Φ^{•}.

Definition 2 (Part 1). Given a binary relation |− on Φ, and a function δ : (Φ × E) → Φ, let |−^{δ} be the binary relation on E defined by

(9)  e |−^{δ} e′ iff δ(⊤, e) |− δ(δ(⊤, e), e′)

where ⊤ is a tautology (i.e., for all φ ∈ Φ, φ |− ⊤).

The idea behind (9) is to disambiguate the succedent e′ relative to the context δ(⊤, e) induced by the disambiguation of the antecedent. The antecedent is assumed, for the sake of simplicity, to be disambiguated relative to the vacuous context ⊤. Such an assumption is harmless, as disambiguation relative to a context ψ can be carried out instead through a function δ′ : (Φ × E) → Φ related to δ by δ′(φ, e) = δ(ψ^{∧}φ, e) for all φ ∈ Φ and e ∈ E. (^{∧} is the merge operation mentioned in the introduction.)

Having extended |− to E relative to a fixed function δ : (Φ × E) → E, let us introduce some variation, by fixing a set Δ of such functions and a family D of (“sufficiently large”) subsets of Δ, passing from |−^{δ} to |−^{D} as in (7).

Definition 2 (Part 2). Given a set Δ ⊆ (Φ × E) → Φ of functions from Φ × E to Φ, and a family D of subsets of Δ, let |−^{D} be the binary relation on E (extending the binary relation |− on Φ) satisfying

(10)  e |−^{D} e′ iff {δ ∈ Δ : e |−^{δ} e′} ∈ D

for all e, e′ ∈ E.

It is now a simple exercise to formulate the aforementioned notions |−_{QQ′} as |−^{D}.

Proposition 3. Given a function δ̂ : E → Pow(Φ), let Δ be the set of (all) functions δ : (Φ × E) → Φ such that for all φ ∈ Φ and e ∈ E, δ(φ, e) ∈ δ̂(e).

Then the relations |−_{QQ′} and |−^{D}, specified (respectively) by (6) and (10), coincide, assuming that

(i) for Q = Q′ = ∀, D is {Δ} (ii) for Q = Q′ = ∃, D is {D ⊆ Δ : D ≠ ∅} (iii) for Q = ∀ and Q′ = ∃, D is the set of all sets D ⊆ Δ such that

(∀e ∈ E) δ̂(e) = {δ(⊤, e) : δ ∈ D}

and (iv) for Q = ∃ and Q′ = ∀, D consists of all sets D ⊆ Δ such that for all

e, e′ ∈ E, there is a δ ∈ D such that

δ̂(e′) = {δ′(δ′(⊤, e), e′) : δ′ ∈ D and
δ′(⊤, e) = δ(⊤, e)} .

Observe that in Proposition 3, δ̂ requires only of each δ ∈ Δ that δ(φ, e) ∈ δ̂(e), imposing no constraints whatsoever on φ. This reflects the absence of “connections between interpretive choices” in |−_{QQ′}. The context-dependence of the disambiguations in D is employed in Proposition 3 only as a technical device to reduce the two parameters Q and Q′ to a single parameter D (whose elements δ have an extra argument for contexts).

In accordance with the intuition that D consists of the “sufficiently large” subsets of Δ, it is natural to require of the family D in Definition 2 (Part 2) that (C1) Δ ∈ D (since e |−^{D} e′ ought to hold if for every δ ∈ Δ, e |−^{δ} e′) and (C2) for all subsets D_{1} and D_{2} of Δ, if D_{1} ∈ D and D_{1} ⊆ D_{2}, then D_{2} ∈ D (since e_{2} |−^{D} e′_{2} should follow if e_{1} |−^{D} e′_{1} and whenever e_{1} |−^{δ} e′_{1}, e_{2} |−^{δ} e′_{2}). Note that for each of the four cases in Proposition 3, D meets conditions (C1) and (C2).

Reflecting further on Definition 2, observe that each disambiguation δ ∈ Δ is total insofar as the range of δ is Φ. A notion of partial disambiguation is, however, implicit in Pow(Δ); that is, a subset D of Δ can be regarded as a partial disambiguation (under the common reduction of a partial object to the set of its completions). Indeed, D can be thought of simply as the set of partial disambiguations D covering enough of Δ such that for all e, e′ ∈ E, if for every δ ∈ D, e |−^{δ} e′, then e |−^{D} e′. Given that, in practice, disambiguation is partial, it makes sense to step one level up in abstraction and reconsider our extensions of [[·]] to Φ^{•}, by passing to a set O of binary relations ≺ on Φ^{•}. As it turns out, this leads us back to the issue (broached in line (5) in §2.1) of compositional semantics.

2.3. Partial disambiguations and semantic interpretations. The basic problem in generalizing (1) to a notion of partial (rather than total) disambiguation, given by a set O of binary relations on Φ^{•}, is indicated by the question mark “?” in

[[φ • φ′]]_{O} = \{ \begin{matrix}[[φ]] & if for every ≺ in O, φ ≺ φ′ \\ [[φ′]] & if for every ≺ in O, φ′ ≺ φ \\ ? & otherwise. \end{matrix}

One way to attack “?” is to weaken “every” to some quantifier Q (such as “most”)^{3}

[[φ • φ′]]_{O} = \{ \begin{matrix}[[φ]] & if for Q ≺ in O, φ ≺ φ′ \\ [[φ′]] & if for Q ≺ in O, φ′ ≺ φ \\ ? & otherwise. \end{matrix}

While this may narrow the gap, it will not (in general) close it, especially if we insist that the choice between φ and φ′ be “fair” in the sense that [[φ • φ′]]_{O} = [[φ′ • φ]]_{O}. Of course, rather than choosing between φ and φ′, we might simply fill the gap with say, [[φ ∨ φ′]] or even [[φ ∧ φ′]]. To see why this might not be so far-fetched, let us reconsider [[φ • φ′]]_{≺} and line (1).

The introduction in (1) of the relation ≺ is broadly reminiscent of the addition of an accessibility relation in Kripke’s semantics for modal logic, an essential difference being that ≺ is a relation on formulas, while the accessibility relation is one on worlds. (In this sense, the interpretation of • is just an intensional variation on Kripke’s semantics.) This difference raises the question of analyzing • compositionally under [[·]]_{≺}; that is,

is there a function F_{•} such that for all e and e′ ∈ Φ^{•}, [[e • e′]]_{≺} = F_{•}([[e]]_{≺}, [[e′]]_{≺}) ?

Let us proceed carefully, and spell out an assumption that we have been making all along; the unambiguous nature of formulas in Φ is construed as supporting

Assumption A: [[φ]]_{≺} = [[φ]] for every φ ∈ Φ .

Confining our attention to unambiguous formulas φ, φ′, ψ and ψ′ (∈ Φ), and agreeing that

φ ≡_{0} ψ means [[φ]] = [[ψ]] ,

a necessary condition for the existence of F_{•} is that

φ ≡_{0} ψ and φ′ ≡_{0} ψ′ imply [[φ • φ′]]_{≺} = [[ψ • ψ′]]_{≺} .

This, in turn, suggests (under Assumption A) closing ≺ as follows

(11)  φ ≺ φ′ and φ ≡_{0} ψ ≢_{0} φ′ ≡_{0} ψ′ imply ψ ≺ ψ′ .

But if ψ′ ≺ ψ (as it well could), then (11) would mean that [[φ•φ′]]_{≺} ≠ [[φ′•φ]]_{≺}, which is a rather high price to pay for compositionality. The problem is that the conjunction φ ≺ φ′ and φ′ ≺ φ is compatible with (1) only as long as φ ≡_{0} φ′, which is the case with linear orders (strict or otherwise). As the closure condition suggested by (11) may take us outside the realm of linear orders, it is appropriate to reconsider (1). To the extent that ≺ is intended to disambiguate totally, our modification of (1) should still amount to composing some syntactic function ·_{≺} : Φ^{•} → Φ (that disambiguates totally, in that its range is Φ) with [[·]]. Isolating line (2) of Definition 1, let us weaken it to

3How the choice of Q here relates to the parameter q in |−^{q} (from §2.2) is an obvious question not investigated in the present paper.

(e • e′)_{≺} = \{ \begin{matrix}e_{≺} & if e ≺ e′ but not e′ ≺ e \\ e′_{≺} & if e′ ≺ e but not e ≺ e′ \\ ? & otherwise , \end{matrix}

writing, as before, “?” to indicate doubt. Casting aside such doubts, suppose

(e • e′)_{≺} = \{ \begin{matrix}e_{≺} ∨ e′_{≺} & if neither e ≺ e′ nor e′ ≺ e \\ e_{≺} ∧ e′_{≺} & if both e′ ≺ e and e ≺ e′ , \end{matrix}

modeling (as it were) indifference by disjunction, and conflicts in choices by conjunction. Now, such schemes may well seem unnecessarily complicated, designed for poorly chosen total disambiguations that we would be better off without. But even if we start with “good” linear orders ≺ (suited for the simple scheme (1)), the question of defining [[·]]_{O} relative to a set O of such linear orders leads us back to such complications, if O is reduced either to ⋂ O or ⋃ O (the trouble being that neither the intersection nor the union of a set O of linear orders can be expected to be a linear order). Some motivations for and consequences of collapsing a set of linear orders on Φ^{•} to a binary relation on Φ^{•} are detailed in Fernando [6], where an arbitrary binary relation R on Φ^{•} is modified in a minimal way to support a compositional analysis of • under a revised interpretation [[·]]_{R} of (1) along the lines described above — i.e., using ∨ and ∧.

But returning to the question of [[·]]_{O}, does resolving “?” through ∨ or ∧ (or any unambiguous construct, for that matter) do justice to the intuition that O is a partial disambiguation? What is so troubling here is that within the scheme sketched above, [[·]]_{O} is the composition [[·_{O}]] of some function ·_{O} : Φ^{•} → Φ with [[·]] (just as, in §2.1, [[·]] is extended to Φ^{•} by pre-composing it with the function ·_{≺} specified in Definition 1). The fact that the range of ·_{O} is Φ betrays the total, rather than partial, character of the disambiguation effected. The obvious alternative is to let the range of ·_{O} spill over into Φ^{•}, as in the following variation on Definition 1.

Definition 3. Given a set O of binary relations on Φ^{•}, let ·_{O} be the function on Φ^{•} given inductively by

φ_{O} = φ for φ ∈ Φ
(12)  (e • e′)_{O} = \{ \begin{matrix}e_{O} & if Q ≺ in O, e ≺ e′ \\ e′_{O} & if Q ≺ in O, e′ ≺ e \\ e_{O} • e′_{O} & otherwise. \end{matrix}
γ(e, …, e′)_{O} = γ(e_{O}, …, e′_{O}) for every

connective/quantifier γ in Φ .

For definiteness, the quantifier Q in (12) might be set simply to ∀. The main point is that (12) gets rid of as many occurrences of • as it can (under some choice of Q), but might still leave some behind. Now, because ·_{O} may output an expression in Φ^{•} −Φ, it cannot simply be composed with the interpretation function [[·]] for Φ. Instead, writing V for the range of the function [[·]] and D for the set of partial disambiguations O,^{4} let us compose ·_{O} with a function [[·]]^{•} : Φ^{•} → X, where X satisfies the reflexive domain equation

(13)  X = V + (D → X)

and

(14)  [[φ]]^{•} = [[φ]] for φ ∈ Φ
[[e • e′]]^{•} = the function β : D → X such that

β(O′) = [[(e • e′)_{O′}]]^{•} (15)

[[γ(e, …, e′)]]^{•} = F_{γ}^{X}([[e]]^{•}, …, [[e′]]^{•}) for each

(16) connective/quantifier γ in Φ .

(16) requires that each F_{γ} (interpreting γ relative to [[·]]) be lifted to an operation F_{γ}^{X} on X,^{5} while (15) simply stalls the disambiguation of e • e′, leaving to some O′ ∈ D its (partial) disambiguation (as described in (12)). As the references to D in (13) and (15) make clear, syntax plays a prominent role in [[·]]^{•}. Can we wash away such traces of syntax (in [[·]]^{•}) by replacing expressions e with their semantic values [[e]]^{•}?

This is a delicate question already for unambiguous formulas. Their interpretation under line (14) is just Assumption A adapted to partial disambiguations O. But disambiguation, whether it be partial or total, may require of an unambiguous formula φ more than the truth-conditional content typically comprising [[φ]]. Consider again the example (U1) • (U2) mentioned in §1.2, comparing its disambiguation within

 (A5) Many people at work are fond of all kinds
           of vegetables.  Many also are sports
           enthusiasts.  Dorit likes swimming.
           Josef loves squash.

to that within

 (A6) Many people at work are sports enthusiasts.
           Dorit likes swimming.  Many also are fond
           of all kinds of vegetables.  Josef loves
           squash.

4E.g., D = Pow(Pow(Φ^{•} × Φ^{•})), although we might be pickier and accept only certain families of certain binary relations on Φ^{•}.

5Let us not get distracted here by the details of how to implement (13) and (16), as an altogether different approach will soon be pursued.

It is natural to assume that (U1)• (U2) should be disambiguated as (U1) in (A5), and (U2) in (A6), even though the first three sentences of (A5) and (A6) may well be reduced to unambiguous formulas equated by [[·]].^{6} Of course, there would be no problem, should [[·]] happen to be sufficiently fine-grained; but then how would we know that?

Caution suggests that we suspend any commitment to (14) or Assumption A, and that we consider a more general approach to compositionality covering the possibility that the mapping [[·]] abstracts away too much for disambiguation. Towards that end, another shift in our conception of disambiguation is useful — a shift that merges the context-dependence mentioned in §2.2 (and more recently brought out by (A5) and (A6) above) with the partiality hinted at by Definition 3. Taking up context-dependence first, let us extend the binary “merge” operation ^{∧} on Φ to a binary operation ^{∧_{a}} so that our analysis in §2.2 of the discourse (A2) can be reformulated as

(U3) ^{∧_{a}} ((U1) • (U2)) = (U3)^{∧}(U1) .

That is, relating ^{∧_{a}} to line (8) of §2.2,

(U3) ^{∧_{a}} ((U1) • (U2)) = (U3) ^{∧} ((U1) • (U2))_{≺^{(U3)}} ,

where (U1) ≺^{(U3)} (U2). The result of applying φ^{∧_{a}}e is, in this case, an unambiguous formula (in Φ). In contrast to §§2.1 and 2.2, however, we will not insist that the result of such an operation always be unambiguous, construing the disambiguation effected by ^{∧_{a}} instead as partial. This would allow, for instance, ^{∧_{a}} to preserve the lexical ambiguity of word squash in the following fragment of the discourse (A4) in §1.2

 (A7)  Josef loves squash.  Simone can't stand it.

(A7) suggests the possibility that the first argument of^{∧_{a}} (also) be ambiguous. Furthermore, that ambiguity can be resolved in cases such as the discourse formed in §1.2 from (A1) and (A3), where the disambiguation is mutual

((U1) • (U2)) ^{∧_{a}} (A3) = (U2)^{∧}(Josef eats the

                                vegetable squash raw) .

In general then, let us take ^{∧_{a}} to be some binary operation extending ^{∧} to E that partially, if not completely, disambiguates the combination of its two arguments.

But where does ^{∧_{a}} come from, and what exactly does a mean? We will put these questions off to §4, and only assume, for now through the next section, that such an operation on E is, along with the interpretation [[·]] of the set Φ of unambiguous formulas, given (somehow). We will content ourselves with the challenge of defining an interpretation [[e]]_{a} of an expression e that supports a compositional interpretation of ^{∧_{a}} (and perhaps other functions on E), incorporating, if necessary, more structure (for e = φ ∈ Φ) into [[φ]]_{a} than [[φ]]. That is, rather than tampering with a given notion of disambiguation, we will refine the equivalence induced by [[·]] (and denoted ≡_{0} above), possibly at the expense of (14) and Assumption A.

6Perhaps more familiar and convincing examples of the extra-truth-conditional requirements of disambiguation involve pronominal anaphora resolution; the disambiguation of a pronoun such as he is obviously sensitive to (among other things) the order in which discourse referents are introduced.

3. Broadening the context for compositionality

Let E ⊃ Φ be a set of expressions that include not only every φ ∈ Φ, subject to an “interpretation” function [[·]] : Φ → V (to a set V of “semantic values”), but also ambiguous expressions (not necessarily constructed from unambiguous formulas [in Φ] through •). For the record, let us state that a function [[·]]_{a} with domain E is compositional with respect to (or is said to “support a compositional interpretation of”) a family F of (multi-ary) functions on E if for every natural number k and every k-ary function f : E^{k} → E on E in F, there is a k-ary function F_{f} on the range of [[·]]_{a} such that for all e_{1}, …, e_{k} ∈ E,

(17)  [[f(e_{1} …, e_{k})]]_{a} = F_{f}([[e_{1}]]_{a}, …, [[e_{k}]]_{a}) .

In establishing the compositionality of [[·]]_{a}, it suffices to consider the equivalence relation ≡_{a} on E that captures the equations induced by [[·]]_{a} as follows:

e ≡_{a} e′ iff [[e]]_{a} = [[e′]]_{a}

for all e, e′ ∈ E. An equivalence relation ≡ on E is a congruence relative to a k-ary function f on E if

\frac{e_{1} ≡ e′_{1} e_{2} ≡ e′_{2} ⋯ e_{k} ≡ e′_{k}}{f(e_{1}, e_{2}, …, e_{k}) ≡ f(e′_{1}, e′_{2}, …, e′_{k})}

for all e_{1}, e_{2}, …, e_{k}, e′_{1}, e′_{2}, …, e′_{k} ∈ E. Let us say that ≡ is a congruence relative to F if it is a congruence relative to every function in F. Clearly, a function [[·]]_{a} on E is compositional with respect to F iff ≡_{a} is a congruence relative to F. Conversely, given a congruence ≡_{a} (on E) relative to F, we can define a function [[·]]_{a} on E that is compositional with respect to F by (the “term model” construction)

[[e]]_{a} = {e′ ∈ E : e ≡_{a} e′} .

The two extreme examples of equivalence relations on E, namely, the universal relation E × E and the equality relation on E, are congruences relative to F (for any F). Neither describes a non-trivial equational theory over E; the latter adds nothing to syntactic identity (raising the question: what light does semantics throw on syntax, if it is just syntax renamed?^{7}), whereas the former lumps together all expressions in a single undifferentiated mass. The question is what distinctions between expressions ought to be drawn by the semantic equivalence ≡_{a}?

7In this regard, the present section (§3) should be contrasted with Zadrozny [17], where the equivalence induced is syntactic identity.

It is here where the interpretation [[·]] of the subset Φ of (unambiguous formulas in) E enters the picture. If [[·]] interprets two unambiguous formulas φ and φ′ differently — i.e., [[φ]] ≠ [[φ′]] —, then they ought not to be equated, qua expressions in E. (Note that this condition is a weakening of Assumption A from §2.3.) That is, the semantics [[·]]_{a} of ambiguous expressions can be grounded on the interpretation [[·]] of unambiguous formulas by requiring that ≡_{a} be (set-theoretically) contained in the equivalence relation

R = {(φ, φ′) ∈ Φ × Φ : [[φ]] = [[φ′]]} ∪

((E − Φ) × (E − Φ)) (18)

on E. Assuming that we wish to make as few semantic distinctions as possible — otherwise, we may as well take ≡_{a} to be syntactic identity and go home —, the idea is to equate ≡_{a} with the largest equivalence relation on E contained in R that is a congruence relative to F.

But just what, by the way, is F? §3.1 proceeds without making any assumptions about F. In §§3.2 and 3.3, we specialize on the case in which F is the singleton family {^{∧_{a}}}, where ^{∧_{a}} is the binary operation described at the end of §2.3. That choice can be motivated by considering how compositionality can be employed as a constraint on the interpretation [[e]]_{a} of an arbitrary expression e. To be specific, [[e]]_{a} can be put in either

(i) the lefthand side of (17) — i.e., taking e to be equal to f(e_{1}, …, e_{k}) for

some k-ary function f ∈ F and e_{1}, …, e_{k} ∈ E — or

(ii) the righthand side of (17) — i.e., choosing some k-ary function f ∈ F

and e_{1}, …, e_{k} ∈ E, where e = e_{i} for some i ∈ {1, … k}. Option (i) analyzes e in terms of its parts, suggesting globally (i.e., for all e’s) an inductive definition, starting from simple atomic expressions (the base case) and building up to more complicated ones given by F (the inductive case). It is perhaps fair to say that a good deal of the “computational” interest in compositionality lies in the way it is (in practice) established by such an inductive procedure. Nonetheless, a complementary co-inductive approach that is also illuminating is suggested by option (ii), under which the operation ∧_{a} can be viewed as a “master” disambiguating function f that merges e with other expressions. For instance, whereas (A1) (from §1.2) is broken apart, under the inductive definitions of §2, as (U1)•(U2), it can also be embedded within larger discourses such as (A2) and (A4) (as well as (A5), (A6) and (A7), at the end of §2.3).^{8} It is largely the latter (co-inductive) approach that the present section pursues.

8As options (i) and (ii) are just different sides of the one coin of compositionality, the division outlined (i.e., according to which side of (17) we put e) should not be taken too seriously. What ought not to be brushed aside lightly is the genuine technical difference between induction and co-induction (i.e., between least and greatest fixed points; see, e.g., Aczel [1]), which distinguishes §§2 and 3.

§3.1 is quite abstract and general, sidestepping a direct definition of a (semantic) interpretation [[e]]_{a} of expressions e ∈ E, by setting its sights more modestly on an equivalence relation ≡_{a} on E (which, as we have already noted, is sufficient for the purpose of establishing compositionality). The reader with little patience for abstractness is asked to focus here on the case where F is {^{∧_{a}}} and the equivalence relation R is that induced by [[·]] according to (18). That case will be fleshed out further in §3.2, which considers definitions of [[·]]_{a} approximating the intuition that [[e]]_{a} is the set of disambiguations of e, for an appropriate notion of disambiguation based on ^{∧_{a}}. Curiously, in looking more closely at ^{∧_{a}}, §3.3 edges back to an inductive analysis, in which the additional generality of §3.1 is exploited (§4.1).

3.1. An abstract equivalence on expressions. Suppose that an equivalence relation R on E and a family F of multi-ary functions on E are given. Define the set of congruences relative to every function in F that are contained in R

Cng[R, F] = {≡ ⊆ R : ≡ is a congruence relative to F} ,

with the idea of looking at its (⊆-)largest element, if it, in fact, exists. Let us first consider the simple case where F is a singleton {f}, and write Cng[R, f] for Cng[R, {f}].

Lemma 4. For every unary f : E → E and equivalence relation R on E, Cng[R, f] has a largest element.

Proof. The largest element ≡ is easily constructed by co-induction (e.g., Aczel [1]):

≡_{0} = R
≡_{n+1} = {(e, e′) ∈ ≡_{n} : f(e) ≡_{n} f(e′)}
≡ = ⋂_{n<ω} ≡_{n} .

Clearly, ≡ must contain every element of Cng[R, f]. Furthermore,

e ≡ e′ iff (∀n) e ≡_{n} e′
iff eRe′ and (∀n) f(e) ≡_{n} f(e′)
iff eRe′ and f(e) ≡ f(e′)

for all e, e′ ∈ E. ⊣

What if the function f is (say) binary? We might proceed as before, but now taking

≡_{n+1} = {(e, e′) ∈ ≡_{n} : (∀d, d′ s.t. d ≡_{n} d′)
f(e, d) ≡_{n} f(e′, d′) and f(d, e) ≡_{n} f(d′, e′)} .

The problem here, however, is that the occurrence of d ≡_{n} d′ is not positive. Accordingly, we make do with d′ = d, reducing a k-ary function to its unary projections as follows.

Lemma 5. Given a k-ary function f : E^{k} → E on E, an i ∈ {1, …, k} and a (k − 1)-tuple \overline{e} ∈ E^{k−1}, define the function f_{i,\overline{e}} : E → E by

f_{i,\overline{e}}(e) = f(⟨e, \overline{e}⟩_{i}) ,

where ⟨e, \overline{e}⟩_{i} is the k-tuple obtained from \overline{e} by sticking e at its ith position. Then for every equivalence relation R on E,

Cng[R, f] = ⋂_{i∈\{1,... ,k\}} ⋂_{\overline{e}∈E^{k−1}} Cng[R, f_{i,\overline{e}}] .

Proof. The direction ⊆ is immediate from the reflexivity of equivalence relations. For the converse, it suffices to observe that k applications of the rule

\frac{e ≡ e′}{f_{i,\overline{e}}(e) ≡ f_{i,\overline{e}}(e′)} for all i ∈ \{1, …, k\} and \overline{e} ∈ E^{k−1}

and the transitivity of equivalence relations yield

\begin{matrix}e_{1} ≡ e′_{1} \\ \overline{f(e_{1}, …, e_{k}) ≡ f(e′_{1}, e_{2}, …, e_{k})} & e_{2} ≡ e′_{2} \end{matrix}

\begin{aligned}\overline{f(e_{1}, …, e_{k}) ≡ f(e′_{1}, e′_{2}, e_{3}, …, e_{k})} & e_{3} ≡ e′_{3} \\ & ⋮ & e_{k} ≡ e′_{k} \end{aligned}

\overline{f(e_{1}, …, e_{k}) ≡ f(e′_{1}, …, e′_{k})}

or (more concisely)

\frac{e_{1} ≡ e′_{1} e_{2} ≡ e′_{2} ⋯ e_{k} ≡ e′_{k}}{f(e_{1}, e_{2}, …, e_{k}) ≡ f(e′_{1}, e′_{2}, …, e′_{k})} .

⊣

We can now step up from Cng[R, f] to Cng[R, F], where F is a family of multi-ary functions on E.

Theorem 6. For every equivalence relation R on E and family F of multi-ary functions on E, Cng[R, F] has a largest element.

Proof. Let F^{1} be the family of unary projections of functions in F

F^{1} = \{f_{i,\overline{e}} : f is a k-ary function in F and
i ∈ \{1, …, k\} and \overline{e} ∈ E^{k−1}\} .

From Lemma 4, it follows that F^{1} has a largest element, namely

⋂_{f∈F^{1}} largest element of Cng[R, f] ,

which, by Lemma 5, is the largest element of F. ⊣

Remarks.

(i) The intersection formed in the proof of Theorem 6 can be unwound as a co-induction that closes at ω, where

≡_{0} = R
≡_{n+1} = {(e, e′) ∈ ≡_{n} : (∀f ∈ F^{1}) f(e) ≡_{n} f(e′)} .

This more explicit argument is of interest inasmuch as closure at ω provides an upper bound on the complexity of a logic to reason about the largest equivalence in Cng[R, F].

(ii) For R = E × E, the co-induction stops at the earliest possible stage, the largest element of Cng[E × E, F] being just E × E, for any F. By contrast, line (18) bases the semantics of ambiguous expressions on some interpretation [[·]] : Φ → V of a subset Φ of E (ensuring additionally that all elements of Cng[R, F] are congruences relative to connectives on Φ that admit a compositional analysis under [[·]]). The next subsection focuses further on the case where F is the singleton {^{∧_{a}}}.

3.2. Merging under a non-well-founded set theory. Although an interpretation [[·]]_{a} of E can always be derived from an equivalence ≡_{a} on E by (the term model) [[e]]_{a} = {e′ ∈ E : e′ ≡_{a} e}, it can be instructive to explore other interpretations that capture intuitions specific to the set E at hand. In particular, the notion that

(†) an ambiguous expression can be equated with

the set of its disambiguations

is worked out in the present subsection, with the terms “set” and “disambiguation” construed in a slightly enriched way. Very briefly, the word “set” is taken literally, by adopting the theory described in Aczel [1], while “disambiguation” is interpreted as a process, given by iterated applications of ^{∧_{a}}. The idea roughly is to equate two expressions unless differences between them can, by merging expressions, be observed according to the semantics [[·]] of unambiguous formulas.

Proceeding more formally, define, for every collection X, its collection X^{∗} of (finitary) sequences by

X^{0} = {∅}
X^{n+1} = {ρx : ρ ∈ X^{n} and x ∈ X}
X^{∗} = ⋃_{n<ω} X^{n} ,

and write X^{+} for X^{∗} − X^{0}. Next, given a binary function f : (E × E) → E (e.g. ^{∧_{a}}), define its extension f^{+} : E^{+} → E to E^{+} by

f^{+}(e) = e
f^{+}(ρe) = f(f^{+}(ρ), e) ,

and let f^{Φ} be the (graph of the) restriction of f^{+} to elements of E^{+} that outputs values in Φ

f^{Φ} = {(ρ, φ) ∈ E^{+} × Φ : f^{+}(ρ) = φ} .

To a first approximation, the idea is to equate [[e]]_{a} with the set {(ρ, [[φ]]) : (eρ, φ) ∈ f^{Φ}}, where f is ^{∧_{a}}. But to capture the largest congruence relative to f contained in the relation R specified by (18), we need also to “reduce” the sequences ρ in the pairs (ρ, φ) in f^{Φ}. Towards that end, it is useful to appeal to the theory of non-well-founded sets described in Aczel [1], from which the following notions are drawn. Given a collection X of indeterminates, a system of equations over X is a function s with domain X such that for every x ∈ X, s(x) is a set with atoms drawn from X. Such a system s is often presented as x = s(x), the reason being that a solution to that system s is a function ϕ with domain X such that for every x ∈ X, the xth root ϕ(x) is equal to the set obtained from s(x) by replacing every indeterminate x′ occuring in s(x) by ϕ(x′). Returning now to the problem at hand, form the family X_{E} = {x_{e} : e ∈ E} of indeterminates (with x_{e} ≠ x_{e′} whenever e ≠ e′), and define the system s^{f,[[·]]} of equations

x_{e} = {(x_{e_{1}}x_{e_{2}} ⋯ x_{e_{n}}, [[φ]]) : (ee_{1}e_{2} ⋯ e_{n}, φ) ∈ f^{Φ}}

over X_{E}. The Anti-Foundation Axiom (AFA) in Aczel [1] provides a unique solution to any system of equations, such as s^{f,[[·]]}. More abstractly, the roots of s^{f,[[·]]} live in a certain final F -coalgebra, where F is the functor on the category of classes given by

F (X) = Pow(X^{∗} × V)

(recalling that V is the image of [[·]]). Roughly speaking, the more familiar notion of an algebra is dualized to a coalgebra to keep the “final” structure from collapsing to a single point (just as the equivalence relation R constrains the largest element of Cng[R, f]). To be more precise, observe

Proposition 7 (AFA). Given a binary function f : (E × E) → E, a function [[·]] : Φ → V, where Φ ⊆ E, and an e ∈ E, let r_{e} be the x_{e}th root of the system s^{f,[[·]]} of equations (defined above). Then

r_{f(e,e′)} = {(ρ, v) : (r_{e′}ρ, v) ∈ r_{e}}

for all e, e′ ∈ E.

Proof. The proposition follows from proving by a routine induction on n that

f^{+}(ee′e_{1} ⋯ e_{n}) = e_{0} iff f^{+}(f(e, e′)e_{1} ⋯ e_{n}) = e_{0}

for all e, e′, e_{0}, e_{1}, …, e_{n} ∈ E. ⊣

Theorem 8 (AFA). Given a binary function f : (E × E) → E and a function [[·]] : Φ → V, where Φ ⊆ E, let ≡ be the largest element of Cng[R, f], for R given by (18). Then, under the definitions mentioned in Proposition 7,

e ≡ e′ iff r_{e} = r_{e′}

for all e, e′ ∈ E.

Proof. Let ∼ be the equivalence relation on E induced by s^{f,[[·]]}

e ∼ e′ iff r_{e} = r_{e′} .

Clearly, ∼ is contained in R since for every φ ∈ Φ, (φ, φ) ∈ f^{Φ}. Furthermore, it is immediate from the previous proposition that ∼ is a congruence relative to f. It remains to show that ≡ is contained in ∼. Suppose e ≁ e′, and (without loss of generality) say, (ρ, v) ∈ r_{e} − r_{e′}. Then it is easy to see that e ≢_{n} e′, where n is the length of the sequence ρ, and ≡_{n} is as defined in Remark (i) at the end of §3.1. ⊣

Remarks.

(i) It is crucial for the congruence property established in Proposition 7 that the domain of the function f^{Φ} (used to define the system s^{f,[[·]]} of equations) include sequences of length greater than 1.

(ii) As the co-induction underlying the relative consistency proof for AFA does not, in general, close at ω, what is gained by the term construction in §3.1 is a tighter lower bound on the complexity of the equivalence induced by the interpretation.

(iii) L. Moss has pointed out to the author that there is a striking similarity between Theorem 8 and the Myhill-Nerode Theorem on minimum state deterministic finite automaton (see, e.g., Hopcroft and Ullman [11]). Putting aside the finiteness assumptions in the Myhill-Nerode Theorem, it would seem that the construction behind Theorem 8 amounts simply to a straightforward adaptation R_{Φ} of Nerode’s maximal right invariant relation (with acceptance in a language replaced by evaluation to one of infinitely many formulas in Φ up to semantic equivalence)

eR_{Φ}e′ iff (∀x ∈ E^{∗}) (f^{+}(ex) ∈ Φ iff f^{+}(e′x) ∈ Φ)
and (∀φ ∈ Φ)(f^{+}(ex) = φ
implies [[f^{+}(e′x)]] = [[φ]]) .

The critical difference, however, is not just that f (or ^{∧_{a}}) need not be concatenation (or even associative), but that Theorem 8 defines an interpretation based on simultaneously solving a system of equations, with the effect that the equivalence induced by this interpretation need not be the relation R_{Φ} defined above. That is to say, the asymmetry (reminiscent of right invariance) in the definition of the system of equations for Theorem 8 is only apparent: an indeterminate x_{e} in s^{f,[[·]]} occurs not only as the left hand side of an equation, but also in the right hand side of many other equations! The more appropriate notion corresponding to the equivalence induced by the interpretation in Theorem 8 is not Nerode’s right-invariance, but rather Myhill’s two-sided equivalence (Hopcroft and Ullman [11], pages 65 and 74), suitably modified in §3.1 to cover (possibly non-associative) binary functions and more generally k-ary functions (for any finite k).

3.3. Simplifying the set of disambiguations. Reviewing the interpretation in §3.2 of an expression e ∈ E relative to a merge operation^{∧_{a}} : (E×E) → E, the question arises as to whether we can trim down the set of disambiguations to which e is, under the intuition labeled (†) there, equated to some critical characteristic core (sufficient to distinguish e from other expressions). In this connection, two notions of disambiguation can be discerned. For every e ∈ E, define a right disambiguation of e to be a pair (ρ, φ) ∈ E^{∗} × Φ such that f^{+}(eρ) = φ, where f =^{∧_{a}}. That is, a pair (e_{1} ⋯ e_{n}, φ) ∈ E^{∗} ×Φ is a right disambiguation of e iff (⋯ ((e^{∧_{a}}e_{1})^{∧_{a}}e_{2}) ⋯^{∧_{a}} e_{n}) = φ. By contrast, a left disambiguation of e is a pair (e_{1} ⋯ e_{n}, φ) ∈ E^{∗} × Φ such that (e_{2} ⋯ e_{n}e, φ) is a right disambiguation of e_{1} — i.e., (⋯ ((e_{1}^{∧_{a}}e_{2})^{∧_{a}}e_{3}) ⋯^{∧_{a}} e) = φ. An equation

x_{e} = {(x_{e_{1}}x_{e_{2}} ⋯ x_{e_{n}}, [[φ]]) : (ee_{1}e_{2} ⋯ e_{n}, φ) ∈ f^{Φ}}

in the system s^{f,[[·]]} defined in §3.2 encodes the right disambiguations of e; what is perhaps less obvious is that the left disambiguations are also encoded in s^{f,[[·]]} through occurrences of indeterminates x_{e_{n}} to the right of an equation.^{9} Turning to concrete examples from §1.2,

((U3), (U3)^{∧}(U1)) is a left disambiguation of (A1)

(19)

while

       ((A3),(U2)^{∧}Josef eats the vegetable squash raw)

is a right disambiguation of (A1) and

(20) a left disambiguation of (A3).

The notion of a right disambiguation is natural from the point of view of process theory (see, e.g., Aczel [1]), where a process is analyzed in terms of the ways it might evolve with time (i.e., stretching forward to the future). On the other hand, the notion of a left disambiguation comes closer, as pointed out by N. Asher, to intuitions from discourse theory, where an expression e is evaluated relative more often to the context established by the preceding discourse (i.e., looking back at the past) — examples such as (20) notwithstanding. This bias reflects the preference to link pronouns with discourse referents from the past (anaphora), rather than in the future (kataphora).

At any rate, note that in both (19) and (20), the resulting discourse (i.e., the second component of the pair) is obtained by applying the (unambiguous) merge ^{∧} to unambiguous formulas. These examples suggest the possibility that (P0) whenever e^{∧_{a}}e′ ∈ Φ, there are φ, φ′ ∈ Φ such that e^{∧_{a}}e′ = φ^{∧}φ′ . Were (P0) true, we could define a function δ̂: E → Pow(E) postulated by the schemes |−_{QQ′} described in §2.2, satisfying

9This takes us back to Remark (iii) in §3.2, the force of which is that the same equivalence on expressions would be induced by solving a system of equations obtained from turning the right disambiguations in s^{f,[[·]]} to left disambiguations. (Or for that matter, by solving a system of equations that explicitly represents both right and left disambiguations.)

The apparent asymmetry vanishes through the magic of non-well-foundedness. To see what exactly is going on here, non-well-foundedness can be eliminated via §3.1. The key point is that the intersection formed in Lemma 5 must take into account all unary projections.

In this respect, the approach of §3.2 is somewhat misleading, minimizing, as it does, the distinction between left and right disambiguations through the circularity in the equations.

(P1) whenever e^{∧_{a}}e′ ∈ Φ, there is a φ ∈ δ̂(e) and a φ′ ∈ δ̂(e′) such that

e^{∧_{a}}e′ = φ^{∧}φ′. Indeed, we could go further and connect e and e′, if we replace δ̂ by two functions θ, α : (E × E) → Pow(Φ) such that (P2) whenever e^{∧_{a}}e′ ∈ Φ, there is a φ ∈ θ(e, e′) and a φ′ ∈ α(e, e′) such that

e^{∧_{a}}e′ = φ^{∧}φ′ with the intuition that θ(e, e′) is the set of unambiguous formulas to which the e can be reduced, given that e′ occurs to its right, while α(e, e′) is the set of unambiguous formulas to which the e′ can be reduced, given that e occurs to its left.^{10} Examples (19) and (20) suggest

(U1) ∈ α((U3), (A1))
(U2) ∈ θ((A1), (A3))

      Josef eats the vegetable squash raw ∈ α((A1), (A3)) .

Our treatment of ambiguous expressions in §§3.1 and 3.2 can be labeled as underspecified in two ways; we neither assume

(i) some explicit representation (e.g., via •) of an ambiguous expression e in terms of the set δ̂(e) of unambiguous formulas to which e can be reduced

nor

(ii) the possibility (P0) — equivalently, the existence of functions δ̂, α and

θ verifying (P1) and (P2). The abstract notion of disambiguation §3.2 associates with (†) is very different from δ̂ or even θ and α. The sets [[e]]_{a} given by the x_{e}th-roots of s^{f,[[·]]} are not just — like δ̂(e) — subsets of Φ, but quite hairy beasts. For an arbitrary binary function f on E, it is difficult, if not impossible, to sort out the contributions that e, as opposed to some e′ ∈ E, makes to f(e, e′), or to [[f(e, e′)]], whenever f(e, e′) should happen to fall in some designated subset Φ of E (on which [[·]] is defined).

10There is little point in mentioning δ̂ or α and θ if we know nothing more about them than (P1) or (P2). Some form of converse to (P1) or to (P2) would be useful to preclude, for instance, δ̂(e) = α(e, e′) = θ(e, e′) = Φ for all e and e′ ∈ E. But having failed to formulate some such simple condition, I must appeal instead to the reader’s command of English to make more refined choices of δ̂, α and θ. In particular, we should resist reducing say, α to θ by setting α(e, e′) = θ(e′, e), in view of the difference between (A8)  She seemed happy.  A woman stopped to chat.

and (A9)  A woman stopped to chat.  She seemed happy.

The thrust of §3 is not, however, to deny the plausibility of (P0) for ambiguous expressions in natural language, only to investigate just how far we can get without appealing to (P0). It is a very different matter to rule out (P0); that would be a most radical form of underspecification. And it would be quite difficult to defend, if only because we would be hard-pressed, under such a view, to compute ^{∧_{a}} (never mind, some notion ≡_{a} of equivalence on E that presupposes ^{∧_{a}}).

4. Discussion

Summarizing §§2 and 3, one might say the following. An expression is ambiguous precisely because, in isolation (i.e., without disambiguating information), its meaning is indeterminate, although it may, by merging with other expressions, produce a piece of discourse with a determinate meaning. The question is whether that meaning can be decomposed into discernible parts, isolating the contributions made by the pieces constituting the discourse. Put technically, a general co-inductive analysis of an ambiguous merge is presented in §3, but the problem of providing an inductive characterization of that merge is left open.

Is the summary above coherent? The matter might be clearer perhaps if we pay careful attention to the distinction between (on the one hand) syntax (i.e., the expressions in E and ^{∧_{a}}) and (on the other hand) semantics (i.e., the meanings as specified, and connected to the syntactic material E, by [[·]] and [[·]]_{a}). What may be puzzling is that §3 treats E and ^{∧_{a}} as black boxes, but at the same time presumes to analyze these “semantically.” All the definitions highlighted in §2 (viz., Definitions 1, 2 and 3), plus the notions of left and right disambiguation from §3.3 are purely syntactic, and neither mention semantic notions nor enter into the semantic deliberations in §§3.1 and 3.2. The obvious question is what could semantics have to do with disambiguation?

It is not my intention to argue that there is more to disambiguation than manipulations on E. Indeed, I would not deny (nor contend) that all the computational action takes place inside what §3 takes to be black boxes (viz., E and ^{∧_{a}}). That could well be true, but there is also the problem of understanding all that syntax! As expressions may get quite unwieldy, semantics could play a useful role by abstracting away inessential syntactic details,^{11} imposing, as it were, some discipline on the chaos of syntax. Furthermore, to the extent that E and ^{∧_{a}} are theoretical constructs, there is some leeway in defining them; and here semantics may exert some influence (albeit perhaps behind the scenes). More concretely, recall Assumption A (from §2.3) and our decision to relax it, leading to the abstract investigations of §3. We return presently to the inductive generation of E, and an analysis of ^{∧_{a}} based, in no small measure, on semantic considerations centering around context.

11Under this picture, the coarser the semantic equivalence, the more work semantics has put to cleaning up after syntax — hence, the interest in §3 in the largest element of Cng[R, F].

4.1. Ambiguous connectives for dynamic semantics. Recall that the intuition behind ^{∧_{a}} is that it is an extension of the merge ^{∧} on Φ to E that partially (if not completely) disambiguates arguments in E − Φ. No mention of ^{∧} is, however, made in §3 before §3.3, and, indeed, precious little about ∧ is said anywhere above, other than it being some binary operation on Φ. We have been quite vague, for instance, about whether or not ^{∧} is (like ∨) one of the connectives γ of Φ mentioned in Definitions 1 and 3. In Discourse Representation Theory (DRT, Kamp and Reyle [12]), ^{∧} is not — even under a loose reading of “connective” allowing for the division between so-called discourse representations structures and conditions. It will be convenient in what follows, however, to construe ^{∧} as a binary connective not only of Φ but also of E; that is, let us assume that for all e, e′ ∈ E, the string e^{∧}e′ is an element of E. This practice should not cause any confusion, because e^{∧}e′ will be assigned a meaning below faithful to an informal reading of the string as e juxtaposed (or concatenated) with e′ (as is the case with ^{∧}, qua binary operation on Φ). Now, building on postulate (P2) from §3.3, the idea is to set

e^{∧_{a}}e′ = θ_{a}(e, e′) ^{∧} α_{a}(e, e′)

for all e, e′ ∈ E, where θ_{a} and α_{a} are two binary functions on E similar (respectively) to θ and α (from §3.3), but with range equal to E (rather than to Pow(Φ))

θ_{a}(e, e′) ≈ a partial (if not total) disambiguation of e

given that e′ occurs to its right

α_{a}(e, e′) ≈ a partial (if not total) disambiguation of e′

given that e occurs to its left .

This description will presently be made rigorous by a definition, the thrust of which is to unify, under a common system of connectives, our approaches to ambiguity via ^{•} and via ^{∧_{a}}. An example might ease digestion.

Just how pronouns link up with discourse referents (or variables) is left out of accounts such as Barwise [3] and Groenendijk and Stokhof [9], which concentrate instead on formalizing the introduction of a discourse referent z by a random assignment z :=?, leaving later linkages to that variable z to magic. Without attempting to spell out that “magic”, let us record the appeal to it, by providing a semantics for the expressions x =? used in Kamp and Reyle [12] for pronouns that need to be linked with some such variable z. In this way, the constructs •, ^{∧} and x =? can be viewed as forms (respectively) of disjunction, conjunction and existential quantification, introduced to account for ambiguity. Consider again the ambiguous statements (A1) and (A3) from §1.2, and assume that these can be formulated in isolation as (using more logiclike notation, and some simplifications sound for this particular example)

z :=? ^{∧} z′ :=? ^{∧} Josef(z) ^{∧} (squash_{v}(z′) • squash_{s}(z′))
∧ like(z, z′)

and

x =? ^{∧} x′ =? ^{∧} eat-raw(x, x′)

respectively. The two-sentence discourse formed from (A1) and then (A3) can be analyzed as

(z :=? ^{∧} z′ :=? ^{∧} Josef(z) ^{∧} (squash_{v}(z′) • squash_{s}(z′))
∧ like(z, z′)) ^{∧} (x =? ^{∧} x′ =? ^{∧} eat-raw(x, x′)) ,

which reduces to

(z :=? ^{∧} z′ :=? ^{∧} Josef(z) ^{∧} squash_{v}(z′) ^{∧} like(z, z′)) ^{∧}
(x = z ^{∧} x′ = z′ ^{∧} eat-raw(x, x′)) ,

under a particular disambiguation strategy a that specifies a choice of squash_{v}(z′) over squash_{s}(z′), and a resolution of x =? and x′ =? to x = z and x′ = z′, respectively.

Definitions 1 and 3 (from §2) suggest a decomposition of e^{∧_{a}}e′ into (e^{∧}e′)_{a}, for some function ·_{a} : E → E. But in order to accomodate contextual contributions to disambiguation, let us expand ·_{a} into a function from E × E × E to E such that for all l, e, r ∈ E,

(l, e, r)_{a} ≈ the expression to which a reduces e, given that

l occurs to e’s left, and r occurs to its right

and, in particular,

θ_{a}(e, r) = (⊤, e, r)_{a}
α_{a}(l, e) = (l, e, ⊤)_{a}

for some (contentless) tautology ⊤ in Φ (such that [[⊤^{∧}φ]] = [[φ^{∧}⊤]] for every φ ∈ Φ).

Definition 4. Given some set X of variables and some set Φ of formulas (over X)^{12} closed under a set of connectives that includes ^{∧} and ¬, let E be the set of expressions obtained by closing Φ ∪ {‘x =?’ : x ∈ X} under the connectives ∧, ¬ and, in addition, a binary connective •. Suppose also that a is a pair consisting of

(i) a function from triples (x, l, r) ∈ X×E×E to expressions ψ_{a}(x, l, r) ∈ E

and

(ii) a function from pairs (l, r) ∈ E × E to asymmetric binary relations ≺_{a}^{l,r} on E.

12To capture first-order logic, it is useful (following Groenendijk and Stokhof [9]) to assume that for every x ∈ X, the random assignment x :=? is an (atomic) element of Φ.

Define (·, ·, ·)_{a} : (E × E × E) → E by induction on the second argument as follows:

(l, φ, r)_{a} = φ  for φ ∈ Φ
(l, x =?, r)_{a} = ψ_{a}(x, l, r)
(l, e • e′, r)_{a} = \{ \begin{matrix}(l, e, r)_{a} & if e ≺_{a}^{l,r} e′ \\ (l, e′, r)_{a} & if e′ ≺_{a}^{l,r} e \\ (l, e, r)_{a} • (l, e′, r)_{a} & otherwise \end{matrix}
(l, e^{∧}e′, r)_{a} = (l, e, e′^{∧}r)_{a} ^{∧} (l^{∧}e, e′, r)_{a}
(l, ¬e, r)_{a} = ¬(l, e, r)_{a} .

Observe that Definition 4 does not so much extend a as it repackages it, as is obvious from the clause for (l, e^{∧}e′, r)_{a} (the righthand side of which simply shifts the complexity to the first and third arguments of (·, ·, ·)_{a}). The point of the repackaging is to set the stage for a compositional analysis of ambiguous expressions (relative to a). A natural notion of semantic equivalence for the expressions specified in Definition 4 can be derived from an interpretation [[·]] : Φ → V via Theorem 6 (from §3.1), with R as in (18), and F including (·, ·, ·)_{a}, •,^{∧} and the other connectives of Φ. The change in semantics induced by ambiguity is bound to be non-trivial; not even the associativity of (the semantic interpretation of) ^{∧_{a}} can be taken for granted. (Compare, from §1.2, (U3)^{∧_{a}}((A1)^{∧_{a}}(A3)) with ((U3)^{∧_{a}}(A1))^{∧_{a}}(A3); and see also Asher [2] and Fernando [5].)

4.2. Between monotonic interpretation and non-monotonic entailment. Beyond providing a compositional analysis of ambiguous expressions, Definition 4 suggests the following notions of monotonicity: a is left-monotonic if for all l, e, r ∈ E,

(l, e, r)_{a} ∈ Φ implies (∀e′ ∈ E) (e′^{∧}l, e, r)_{a} = (l, e, r)_{a}

and right-monotonic if for all l, e, r ∈ E,

(l, e, r)_{a} ∈ Φ implies (∀e′ ∈ E) (l, e, r^{∧}e′)_{a} = (l, e, r)_{a} .

An argument that a proper choice of a should validate monotonicity might be based on construing the non-ambiguous character of formulas in Φ to mean that whenever (l, e, r)_{a} does happen to be in Φ, it cannot be re-interpreted, whatever further contextual information to its left or right there might be; otherwise, such an (l, e, r)_{a} should have been set to an element of E − Φ. I am not sure how compelling this reasoning is, as it may be turned into the (absurd?) requirement on a that (l, e, r)_{a} ∈ Φ only when e ∈ Φ (the presumption being that contexts can be expanded indefinitely to reverse an interpretation).

If it is not too implausible to assume that a is monotonic (by choosing a value in E − Φ whenever there is any uncertainty in how to disambiguate an expression), it ought not be too surprising that total disambiguations (which assume values in Φ, even when choices can change, depending on further contextual information) should have non-monotonic consequences. Indeed, a wide variety of non-monotonic consequence relations (in the sense, for example, of Kraus, Lehmann and Magidor [13]) can be represented within Definition 2 (from §2.2), based on disambiguations δ with range equal to Φ. More precisely, so-called preferential consequence relations |∼ on Φ can be reconstructed by taking

φ |∼ φ′ iff φ^{∧}c |−^{D} φ′

for all φ, φ′ ∈ Φ, where c is some “rogue” expression in E − Φ, expressing contextual indeterminacy, and subject to a certain choice of D for Definition 4 (Fernando [7]). In view of the sensitivity of disambiguation to expressions to the right as well as to the left, it is worth pointing out perhaps that the consequent e′ in the judgment e |−^{D} e′ does not have the same status in disambiguating e as it would in e^{∧_{a}}e′, for the truth of e′ ought not to be assumed in deciding whether or not e |−^{D} e′. Nonetheless, Definition 4 does suggest a notion of order for monotonicity. Call a family D of subsets of some set Δ ⊆ (Φ × E) → Φ left-monotonic if whenever e |−^{D} e′, l^{∧}e |−^{D} e′ for every l ∈ E. Similarly, D is right-monotonic if whenever e |−^{D} e′, e^{∧}r |−^{D} e′ for every r ∈ E. Relating the partiality of (·, ·, ·)_{a}, the totality in D, monotonic interpretation and non-monotonic entailment is just one of the many topics that the present paper must leave for further investigation (concerning which a perspective from programming language semantics is offered in the companion paper Fernando [8]).

Acknowledgments. My thanks to N. Asher, H, Kamp, L. Moss, S. Peters and U. Reyle for helpful discussions, and to an anonymous referee for useful suggestions.

References

[1] Peter Aczel. Non-Well-Founded Sets. CSLI Lecture Notes Number 14, Stanford, 1988.

[2] Nicholas Asher. Reference to Abstract Objects in Discourse. Kluwer Academic Publishers, Dordrecht, 1993.

[3] Jon Barwise. Noun phrases, generalized quantifiers and anaphora. In E. Engdahl and P. Gärdenfors, editors, Generalized Quantifiers, Studies in Language and Philosophy. Dordrecht: Reidel, 1987.

[4] Kees van Deemter. Towards a logic of ambiguous expressions. In K. van Deemter and S. Peters, editors, Semantic Ambiguity and Underspecification. CSLI Lecture Notes Number 55, Stanford, 1996.

[5] Tim Fernando. Are context change potentials functions? Manuscript, distributed at a workshop on context dependency in Prague, 1995.

[6] Tim Fernando. A logical connective for ambiguity requiring disambiguation. In J. Groenendijk, editor, Ellipsis, Underspecification, Events and More in Dynamic Semantics. Dyana deliverable R2.2.B, 1995.

[7] Tim Fernando. Non-monotonic consequences of preferential contextual disambiguation. In Proc. Tenth Amsterdam Colloquium. ILLC, University of Amsterdam, 1996.

[8] Tim Fernando. Analyzing ambiguity denotationally, operationally and logically. Manuscript, 1996.

[9] J. Groenendijk and M. Stokhof. Dynamic predicate logic. Linguistics and Philosophy, 14, 1991.

[10] Irene Heim. The semantics of definite and indefinite noun phrases. Dissertation, University of Massachusetts, Amherst, 1982.

[11] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Language and Computation. Addison-Wesley, 1979.

[12] H. Kamp and U. Reyle. From Discourse to Logic. Kluwer Academic Publishers, Dordrecht, 1993.

[13] S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44, 1990.

[14] Massimo Poesio. Semantic ambiguity and perceived ambiguity. In K. van Deemter and S. Peters, editors, Semantic Ambiguity and Underspecification. CSLI Lecture Notes Number 55, Stanford, 1996.

[15] Uwe Reyle. Dealing with ambiguities by underspecification: construction, representation and deduction. Journal of Semantics, 10(2), 1993.

[16] Uwe Reyle. On reasoning with ambiguity. In Proc. of the 7th Conference of the European Chapter of the Association for Computational Linguistics. Dublin, 1995.

[17] Wlodek Zadrozny. From compositional to systematic semantics. Linguistics and Philosophy, 17(4), 1994.

120 Tim Fernando