\underline{\underline{\underline{8}}} Analyzing ambiguity

denotationally, operationally and logically

Abstract. Ambiguous expressions are interpreted relative to notions of disambiguation, conceived as processes, and analyzed, in turn, under denotational, operational and logical perspectives (following the custom in programming language theory).

Keywords. Underspecified representations; discourse interpretation; disambiguation; denotational, operational and logical semantics

1. Introduction

A good deal has been written, under the shadow of Montague semantics, about just how compositional and non-representa-tional Discourse Representation Theory (DRT, Kamp and Reyle [18]) is (or can, in principle, be made). A recent paper, which provides many (other) references, is Muskens [21]. In it is presented a formalism called Compositional DRT , which leaves the question of non-representationality somewhat open, but provides a compositional analysis of (various) sentences that are assumed to come indexed, as in

              Sue^{1} has a pigeon^{2}.  She_{1} feeds it_{2}.

Precisely how the anaphoric linkages are established is left to some magic black box, falling completely outside the scope of the formalism (as has become customary in dynamic semantics). Anaphora resolution is, however, hardly an insignificant matter, having, for instance, been implicated in presupposition projection (van der Sandt [24]). Nor is it a straightforward matter, involving, as it does, the thorny possibility of ambiguity. Setting aside troublesome cases of presupposition that can arguably be ascribed to ambiguity, it is easy to produce simple examples such as

               Ernest has a brother; he feeds him

where it is anyone’s guess, who feeds who.

A formalism covering preferences in anaphora resolution is proposed in Jaspars and Kameyama [17], extending “a fragment of van Benthem’s and de Rijke’s dynamic modal logic with additional preferential operators.” A different approach is pursued in the present paper, which (to simplify notation) builds on first-order-like formulas closer to the reformulation in Groenendijk and Stokhof [14] of a fragment of DRT. Precious little is said below about the (undoubtedly important) problem of preferentially resolving ambiguous pronouns in discourse. The emphasis rather is on shedding some light on basic conceptual questions (such as compositionality and non-representationality) in relation to various forms of ambiguity — be that pronominal, lexical (e.g., river bank versus money bank) or structural (e.g., quantifier scope). Whether or not an instance of ambiguity can be traced to words or to sentential operators, the challenge to compositionality (taken up in §2) is that disambiguation often requires an examination of larger units of discourse.

The reader should be warned that a detailed study of a particular process of disambiguation is not undertaken below. What is offered instead is a hook (onto dynamic semantics) upon which any of one’s favorite disambiguation strategies can be hung, thereby facilitating a comparison of these strategies within dynamic semantics. Disambiguation strategies may differ, for instance, as to monotonicity, an issue discussed in (among other places) Poesio [23]. That issue will be considered in §3 under distinct operational and logical perspectives, bearing also upon the question of non-representationality. But first, let us attend to the more rudimentary matter of assigning an ambiguous expression meaning — that is to say, denotational semantics.

2. Regular constructs for ambiguity

Consider the case of an expression e that is ambiguous (say) between two unambiguous formulas φ and ψ. A first attempt at assigning a meaning to e is to characterize e as the disjunction φ∨ψ. As natural as it may seem, this idea has, nonetheless, been discredited on many grounds (e.g., van Deemter [7]), not the least of which is that whereas e is ambiguous, the disjunction φ ∨ ψ is unambiguous — assuming a compositional analysis of ∨ under which the meaning of φ ∨ ψ is determined (unambiguously) by the meanings of its parts, φ and ψ. That is, more concretely, if the meaning [[ϕ]] of an unambiguous formula ϕ is taken to be the set of “states” in which ϕ is “true” then common practice has it that for all unambiguous expressions φ and ψ,

[[φ ∨ ψ]] = [[φ]] ∪ [[ψ]]

(whence φ ∨ ψ is no more ambiguous than φ ∧ ψ). By contrast, van Deemter [7] (p. 234) proposes a “meta-or” connective | such that

(1)  [[φ|ψ]] = [[φ]] or [[φ|ψ]] = [[ψ]] .

Converting (1) from a disjunction into a definition, and writing • instead of |, Fernando [9] defines the meaning of φ • ψ relative to a binary relation ≺ on unambiguous formulas that chooses between φ and ψ as follows

[[φ • ψ]]_{≺} = \{ \begin{matrix}[[φ]] & if φ ≺ ψ \\ [[ψ]] & otherwise. \end{matrix}

More generally, if [[φ]]_{≺} is set to [[φ]] for every unambiguous formula φ, and ≺ is extended to formulas e and e′ that might be built with •, then

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

(2) is broadly reminscent of Kripke semantics for modal operators, the essential difference being that whereas an accessibility relation is a binary relation on semantic entities (called worlds), the binary relation ≺ in (2) relates the very syntactic entities whose meanings are to be defined. This difference casts doubt on the compositionality of (2): is there a function F_{•} such that for all e and e′,

[[e • e′]]_{≺} = F_{•}([[e]]_{≺}, [[e′]]_{≺}) ?

(The problem is that the test e ≺ e′ in (2) may be impossible to carry out if e and e′ are reduced to [[e]]_{≺} and [[e′]]_{≺} respectively.) Whether or not (2) supports a compositional interpretation of • will obviously depend on ≺; the technical details of that dependence are taken up at some length in Fernando [9] (where slight modifications of (2) are considered).

Turning to the question of which relations ≺ are linguistically reasonable, observe that any number of factors come to play, that together might be conveniently labeled context.^{1} Among these factors is the surrounding text, as can be seen by formulating the discourse

(3)  Ernest has a brother; he is happy

as

            (Ernest^{1} has a^{2} brother; he_{1} is happy) •

(4)  (Ernest^{1} has a^{2} brother; he_{2} is happy)

and comparing

             Ernest has a brother; he is happy;
(5)  he'd feel lonesome otherwise

with

             Ernest has a brother; he is happy;
(6)  Ernest feeds him.

The point of this example is that a preference for an interpretation of (4) relative to a relation ≺ such that

           Ernest^{1} has a^{2} brother; he_{1} is happy ≺

           Ernest^{1} has a^{2} brother; he_{2} is happy

can be maintained under (5) but not under (6). (The reader is invited to cook up examples, where the disambiguating text appears to the left.) The more general question is: can the contribution of the surrounding text to disambiguation be brought within the compass of a compositional analysis of ambiguous expressions?

1The ambiguity connective ♯ of König and Reyle [19] is a notational variant of •, requiring a context κ for interpretation. König and Reyle write [[A_{1}♯A_{2}]]^{κ} for what would be written [[A_{1} • A_{2}]]_{≺^{κ}} in Fernando [9].

To answer this question, it is useful to step back for a moment, and recall what the principle of compositionality says

(C) the meaning of an expression is a function

of the meaning of its parts.

Now given the problem of determining the meaning of an expression e, the usual way to apply (C) is to decompose e into its parts, and determine the meanings of those parts. More specifically, to assign a meaning to an ambiguous expression e, one might build e up from unambiguous parts (with the understanding that a formula is unambiguous precisely because it has a determinate meaning). This is exactly the line taken above in characterizing an expression e ambiguous between φ and ψ as φ • ψ, where the function mentioned in (C) is the connective • (disjunction ∨ having previously been deemed unacceptable). There is, however, another way (C) can be applied to assign e a meaning. Rather than breaking e down into its parts, e can be combined with other expressions to form an unambiguous whole. Consider again the discourse labeled (3) above. In isolation, (3) is ambiguous, having an indeterminate meaning. But when merged with other sentences, as in (5) and (6), (3) becomes unambiguous. Relating this example back to (C) and our arbitrary ambiguous expression e, the point is to identify the “function” mentioned in (C) not with a meta-disjunction • (as in the formalization (4) of (3)), but rather with a dynamic conjunction, denoted ^{∧}, that merges e with other expressions, yielding, in some cases, an unambiguous whole. More formally, writing Φ for the set of unambiguous formulas, and E ⊃ Φ for the union of Φ with the set (E − Φ) of ambiguous expressions, we have

                       Ernest^{1} has a^{2} brother ∈ Φ
                                 he is happy ∈ E − Φ
                he'd feel lonesome otherwise ∈ E − Φ
          Ernest^{1} has a^{2} brother ^{∧} he is happy ∈ E − Φ

but (let us agree)

         (Ernest^{1} has a^{2} brother ^{∧} he is happy) ^{∧}

                   he'd feel lonesome otherwise =

          Ernest^{1} has a^{2} brother ; he_{1} is happy ;

                  he_{1}'d feel lonesome otherwise ∈ Φ .

Now, an assignment of a meaning [[e]]_{∧} to an expression e ∈ E is compositional relative to ^{∧} precisely when the equivalence relation ≡ on E defined by

for all e, e′ ∈ E,  e ≡ e′ iff [[e]]_{∧} = [[e′]]_{∧}

is a congruence relative to ^{∧} — i.e., for all e_{1}, e′_{1}, e_{2}, e′_{2} ∈ E,

e_{1} ≡ e′_{1} and e_{2} ≡ e′_{2} imply (e_{1}^{∧}e_{2}) ≡ (e′_{1}^{∧}e′_{2}) .

Of course, for the meaning [[e]]_{∧} of e to “respect” the meaning [[φ]] of an unambiguous formula φ (∈ Φ), we should at the very least require that

(7)  for all φ, ψ ∈ Φ,  φ ≡ ψ implies [[φ]] = [[ψ]] .

Strengthening (7) to a bi-conditional is problematic, as there need not exist a congruence ≡ relative to ^{∧} satisfying the converse of (7) (i.e., the requirement that [[·]]_{∧} be compositional may well be incompatible with the condition that for all φ ∈ Φ, [[φ]]_{∧} = [[φ]]). On the other hand, not only is a congruence relative to ^{∧} satisfying (7) guaranteed to exist, but there is, in fact, a (⊆- )largest one, which constitutes a natural notion of semantic equivalence on E. The gory details are spelled out in Fernando [10]; let us mention only a few concepts from that work which will be useful for the sequel.

Keeping in mind that an expression may become unambiguous only after it is merged with some finite number of expressions, let us define a left ^{∧}- disambiguation of an expression e ∈ E to be a pair (e_{1} ⋯ e_{n}, φ) ∈ E^{∗} ×Φ, the first component of which can be put to the left of e to yield an unambiguous formula, given by the second component of the pair — i.e.,

(⋯ (e_{1}^{∧}e_{2})^{∧} ⋯ ^{∧}e_{n})^{∧}e = φ .

For example, if e_{1} is Ernest^{1} has a^{2} brother, e_{2} is he is happy, and φ is

    Ernest^{1} has a^{2} brother; he_{1} is happy; he_{1}'d feel lonesome
                           otherwise

then (e_{1}e_{2}, φ) is a left ^{∧}-disambiguation of

                 he'd feel lonesome otherwise.

Similarly, call a pair (e_{1} ⋯ e_{n}, φ) ∈ E^{∗} × Φ a right ^{∧}-disambiguation of an expression e ∈ E if

(⋯ (e^{∧}e_{1})^{∧} ⋯ ^{∧}e_{n−1})^{∧}e_{n} = φ .

Taking the pathological case where n = 0, and writing ∅ for the null sequence, note that for any e ∈ E,

(∅, e) is a right ^{∧}-disambiguation of e iff
e ∈ Φ (i.e., e is unambiguous) iff

(∅, e) is a left ^{∧}-disambiguation of e .

For an ambiguous expresion e, however, the case of n > 0 is necessary, and both left and right ^{∧}-disambiguations are useful to test the two argument places of ^{∧}. (Obviously, it would be absurd to assume that ^{∧} is commutative.) Indeed, we may wish to apply sequences e_{1} ⋯ e_{n} and e_{n+1} ⋯ e_{n+m} of expressions to the left and right of e, the crucial point being that the result be unambiguous

(⋯ (((⋯ (e_{1}^{∧}e_{2})^{∧} ⋯ ^{∧}e_{n})^{∧}e)^{∧}e_{n+1})^{∧} ⋯ ^{∧}e_{n+m}) ∈ Φ .

In the absence of the assumption that ^{∧} is associative, there are also variations in parenthesization to consider, leading to a proliferation of notions of disambiguation. Fortunately (and somewhat surprisingly perhaps), the intuition that

(S) the meaning of an ambiguous expression e is

the set of its disambiguations

can be formalized simply enough, with

(i) “set” construed literally albeit non-standardly under a conception al-

lowing for non-well-foundedness (Aczel [1]), and

(ii) “disambiguation” derived from a right^{2} ^{∧}-disambiguation (e_{1} ⋯ e_{n}, φ)

of e, by turning each e_{i} into its meaning, and φ into [[φ]]. That is, within the set theory described in Aczel [1], an ambiguous expression e can be assigned a meaning [[e]]_{∧} such that, in accordance with (S),

[[e]]_{∧} = {([[e_{1}]]_{∧} ⋯ [[e_{n}]]_{∧}, [[φ]]) : (e_{1} ⋯ e_{n}, φ) is

(8) a right ^{∧}-disambiguation of e} .

By contrast, observe that characterizing an expression e ambiguous between φ and ψ as φ • ψ corresponds, under (S), to setting

the meaning of e = {[[φ]], [[ψ]]} ,

which provides no clue at all as to when e can be reduced to φ, and when it must be reduced to ψ. On the other hand, what is funny about (8) is that given a right ^{∧}-disambiguation (e_{1} ⋯ e_{n}, φ) of e, the meaning [[φ]], buried in the right side of (8), encodes not just e, but also the preceding text e_{1} ⋯ e_{n}. Indeed, the question arises as to whether or not the contribution e makes to φ can be separated out from that of e_{1} ⋯ e_{n}. This, in turn, leads (somewhat belatedly perhaps) to the query, where does ^{∧} come from, in the first place? What makes ^{∧} particularly mysterious is that it may merge two ambiguous expressions e and e′ ∈ E − Φ into an unambiguous expression e^{∧}e′ ∈ Φ. How could ^{∧} be defined by induction on expressions, given that an unambiguous expression e^{∧}e′ can be built from ambiguous parts, e and e′?

To uncover that inductive definition, it is useful to assume that the set E ⊃ Φ of expressions is defined inductively from Φ, with closure conditions for (among other things) binary connectives • and ;. The latter connective is a dynamic conjunction similar to ^{∧}, except that for all e, e′ ∈ E, if e; e′ is unambiguous then so is each of e and e′ — i.e.,

e ∈ E − Φ or e′ ∈ E − Φ implies e; e′ ∈ E − Φ .

To cover examples involving anaphora resolution, let us assume also that for every variable x in some fixed set X, the string x =? is in E. Borrowed from informal DRT practice, the expression x =? is employed to represent an unresolved pronoun (e.g., Asher [4]). More specifically, the idea is that

2It is also possible to use left ^{∧}-disambiguations, instead of right ones. What matters is that the system of equations, the roots of which are the required meanings, is solved simultaneously; see Fernando [10].

             Ernest^{1} has a^{2} brother  ^{∧} he is happy

is equal to

          Ernest^{1} has a^{2} brother ; (he_{1}• he_{2}) is happy

but not to

             Ernest^{1} has a^{2} brother ; he is happy

(where the pronoun he remains un-indexed). Next, to bridge the gap between ∧ and ;, let us specify a certain “disambiguation strategy” a that induces a function (·, ·, ·)_{a} from E × E × E to E, satisfying the intuition 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

where the second argument e occupies, so to speak, center stage. Towards a compositional analysis of expressions, let us define (·, ·, ·)_{a} by induction on its second argument, setting, in particular,

(9)  (l, e; e′, r)_{a} = (l, e, e′; r)_{a} ; (l; e, e′, r)_{a}

(shifting text around so as to reduce the complexity of the second argument). Now, assuming

(†) 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,

we can then define

(10)  (l, x =?, r)_{a} = ψ_{a}(x, l, r)  for every x ∈ X

and

(11)  (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}

(where (11) is well-defined because ≺_{a}^{l,r} is assumed to be asymmetric). For example, let e be the expression

x =? ; happy(x)

formalizing the sentence he is happy, let l be the expression

Ernest(y) ; brother(y, z)

formalizing Ernest has a brother,^{3} and r be the experssion

u =? ; would-feel-lonesome-otherwise(u)

formalizing he'd feel lonesome otherwise. Then our analysis above can be supported by setting ψ_{a}(x, l, happy(x))_{a} to x = y • x = z, and taking

x = y ≺_{a}^{l,r} x = z

so that

(l, x =? , happy(x))_{a} is x = y • x = z
(l, e, r)_{a} is x = y ; happy(x) .

Observe that the function (·, ·, ·)_{a} takes values on E, and not necessarily Φ, allowing disambiguation to be a partial process that unfolds gradually (stretching over any number of neighboring expressions). In isolation, the pronoun he could mean any male, but within the discourse labeled (3) above, he refers either to Ernest or his brother, and within (5), he refers to Ernest. By contrast, observe that van Deemter [7]’s specification (1) of φ|ψ requires that the interpretation function [[·]] be based on a very specific “context” (whatever that might exactly be) which totally disambiguates between φ and ψ. But the more assumptions we make of that context, the less useful that interpretation function becomes. Accordingly, the assumption of total disambiguation built into (1) and (2), is abandoned in (11), which supports instead the possibility of stalling the disambiguation (when, as described by the third case in (11), the expressions l and r to the left and right respectively of the expression e•e′ do not provide sufficient information to choose between e and e′). In this way, our formal picture captures more of the process of disambiguation than an interpretation constrained by (1). For the record, that picture is given by

Definition D. Given some set X of variables and some set Φ of formulas (over X)^{4} 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 •. Then assuming that the condition (†) above holds for some a, define (·, ·, ·)_{a} : (E × E × E) → E by induction on its second argument as follows

3The precise choice of the variables y and z is unimportant here, so long as it does not clash with other choices (following, for example, the novelty-familiarity condition of Heim [15]). The (unambiguous) random assignments y :=? and z :=? employed in the reformulation of DRT in Groenendijk and Stokhof [14] — and not to be confused with ambiguous expressions x =? which lie outside the scope of that reformulation — are suppressed for the sake of simplicity. See footnote 4 below.

4It is useful to assume that, for every x ∈ X, the random assignment x :=?, mentioned in the previous footnote, is an (atomic) element of Φ. This approach (due to Groenendijk and Stokhof [14]) captures “essentially” a first-order fragment of DRT, but throws away the distinction (in DRT) between so-called discourse representation structures and conditions — a distinction arguably useful for disambiguation, as elaborated in Asher and Fernando

(12)  (l, φ, r)_{a} = φ  for φ ∈ Φ
(l, ¬e, r)_{a} = ¬(l, e, r)_{a}

plus the clauses (9), (10) and (11).

Insofar as • can be likened to non-deterministic choice +, ; to concatenation, and · =? to Kleene star ·^{∗}, Definition D might be said to describe a regular language for ambiguity (due to unresolved variables). The defect in this description, however, is that although · =? provides an underspecified representation of an infinitary form of • (just as ·^{∗} does of +), it does not (alas) apply to expressions, and cannot (as pointed out to me by P. Krause) be viewed as an infinite choice over finite iterations (as in the case of ·^{∗}). At any rate, the limited expressive power of regular languages suggests enriching these constructs in order to express more complicated conditions (involving, for example, negation or recursion). Confining our attention to modest extensions, one possibility is to sort the variables according (say) to gender and the singular/plural distinction (to support analyses of she, it, they, etc.)

— a routine step that is no more troublesome than the move from ordinary (unsorted) predicate logic up to many-sorted predicate logic.

Turning to lexical ambiguity, one might apply • to capture two of the common readings of the noun bank as

λz (bank_{$$}(z) • bank_{≈}(z)) ,

and characterize ambiguity in terms of meta-variables, following the approach taken in Alshawi and Crouch [2]. Rather than lifting types by λ-abstraction and passing to meta-variables, we can also adopt a first-order combinatory approach, turning a predicate symbol such as bank_{$$} into a constant symbol bank_{$$}, and reformulating the formula bank_{$$}(z) into the term APP(bank_{$$}, z), for some (partial) binary function symbol APP.^{5} An occurrence of the ambiguous un-indexed word bank can then be formalized as a sorted variable, whose sort restricts it to range over the denotations of bank_{$$}, bank_{≈}, plus whatever other senses the word bank has. In this way, arguably all forms of ambiguity admit a uniform characterization in terms of unresolved variables (complicating, as required, the combinatory manipulations to cover various instances of structural ambiguity).

While the connective • may provide a list of the unambiguous formulas that an ambiguous expression can be reduced to, it is not quite as explicit about how to choose between these unambiguous formulas. This is problematic say, for words which are their own antonyms, constituting, as these do, distinct expressions e and ¬e that may both be formulated as φ•¬φ (for some φ). To avoid such mix-up’s, a different • might be introduced, along with its interpretation ≺, for every disambiguation “method.” Just how many of these there are is unclear to me. While it would seem that one • should suffice for pronominal resolution, and perhaps another for structural ambiguity, cases such as lexical ambiguity look potentially more problematic (an extreme measure for which would be to have one • for each ambiguous word). In any event, for the remainder of the paper, let us keep matters simple and stick to Definition D, in the hope the more general case of multiple •’s is illuminated by the case of a single •.

5The formal approach referred to here goes back to Feferman [8], though is perhaps more commonly associated in the linguistic community with property theory, and appears (in some form) in Asher [4]. What matters is not the technical difference between combinators and λ-abstracts, but rather the move to an expressive untyped theory, supporting self-reference. Furthermore, the formalization within first-order (as opposed to higher-order)

logic follows the spirit of the “dynamic” shift from function application to relational (sequential) composition as the paradigmatic function mapping, according to the principle of compositionality, the meaning of the parts to the meaning of the whole.

Next, let us return to the issue of compositionality. This has figured prominently in motivating Definition D, although we have yet to supply a compositional interpretation of the expressions specified in Definition D. But there exists, by abstract nonsense worked out in Fernando [10] (Theorem 6), a largest equivalence relation ≡_{a} on E that (i) is a congruence relative to (·, ·, ·)_{a} and to each connective of E, and (ii) satisfies

for all φ, ψ ∈ Φ, φ ≡_{a} ψ implies [[φ]] = [[ψ]] .

It follows that the (term model) interpretation [[·]]_{a} : E → Pow(E) given by

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

constitutes a compositional interpretation of E, under Definition D, respecting the meanings [[φ]] of unambiguous formulas φ (∈ Φ). What, however, is perhaps unsatisfying about [[·]]_{a} is that it is thoroughly “representational” (in that it builds the meaning of an expression from other expressions), and applies to any system of interpretations [[φ]] of unambiguous formulas φ, whether or not it has anything at all to do with some conception of truth. Moreover, there is also the presupposition of a disambiguation strategy a mentioned in (†), about which the reader is entitled to inquire.

3. Reasoning with partial disambiguations

There is no denying that Definition D does not reduce the burden of specifying (intuitively) a strategy for disambiguation. The definition of (·, ·, ·)_{a} by induction on the second argument simply shoves the complexity in that argument over to the first and third arguments, forcing a particular interpretation of ; (the interpretation of the constructs • and x =? being given freely by a).^{6} In order to analyze the first and third arguments, it will prove convenient to adjoin an element ⊤ to Φ (corresponding to ∅ in E^{∗}), postulating that for every e ∈ E,

6(·, ·, ·)_{a} is essentially a repackaging of a, and should not, despite appearances, be mistaken for a context-sensitive grammar.

⊤ ; e = e
= e ; ⊤

and setting [[⊤]] = [[true]] (where true is a tautology in Φ). Now, a reduction in the complexity of the first argument of (·, ·, ·)_{a} is effected by imposing on a the (conservative) constraint that for all e, e′ ∈ E,

(e, e′, ⊤)_{a} = ((⊤, e, e′)_{a}, e′, ⊤)_{a} ,

meaning that (⊤, e, e′)_{a} is, for the purpose of left disambiguation, no less informative than e. Similarly, for the third argument (i.e., right side),

(⊤, e, e′)_{a} = (⊤, e, (e, e′, ⊤)_{a})_{a} .

An “incremental” processing of the sequence e; e′ would pre-process the expression e into (⊤, e, ⊤)_{a}, before e′ is known, whereupon e′ is attached to the right of (⊤, e, ⊤)_{a}. Now, in order that

(⊤, e; e′, ⊤)_{a} = (⊤, (⊤, e, ⊤)_{a}; e′, ⊤)_{a} ,

it suffices that a validate the equations

(⊤, e, e′)_{a} = (⊤, (⊤, e, ⊤)_{a}, e′)_{a}
(e, e′, ⊤)_{a} = ((⊤, e, ⊤)_{a}, e′, ⊤)_{a} ,

in which case a can be called incremental (for e, e′). Next, suppose that an expression e is disambiguated fully into an unambiguous expression (l, e, e′)_{a} ∈ Φ, under the assumption that l occurs to its left and e′ to its right. Then the same principle of incrementality above would suggest that for every possible succeding expression r, (l, e, e′; r)_{a} = (l, e, e′)_{a}. That is, a might be required to be right monotonic in the sense that for all l, e, r ∈ E,

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

The corresponding notion of left monotonicity is that for all l, e, r ∈ E,

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

(which would be of interest if the directional bias of processing from left to right is weakened).

Observe that the compositional interpretation [[·]]_{a} of E in §2 does not depend on a respecting any of the constraints mentioned in the preceding paragraph. The justification for these constraints must lie instead with operational intuitions concerning the process of disambiguation. To identify “reasonable” strategies of disambiguation, another source of intuitions that we might tap is truth or logical consequence. Towards that end, rather than proceeding, as in §2, from some completely abstract interpretation [[φ]] of unambiguous formulas φ, let us suppose we are given some binary relation |− ⊆ Φ × Φ of logical consequence between unambiguous formulas, and consider how we might extend it to ambiguous expressions e and e′. Clearly, if we can disambiguate e and e′ to unambiguous formulas φ and ψ respectively, then it is reasonable to call e′ a logical consequence of e exactly when φ |− ψ. So suppose we have (— never mind, from where —) some disambiguating information θ that tells us, given any two expressions e and e′ for which we wish to know if e entails e′, that e is to be disambiguated as the formula θ_{−}(e, e′) ∈ Φ, and e′ as the formula θ_{+}(e, e′) ∈ Φ. Then θ suggests an extension |−_{θ} of |− to E, defined by

e |−_{θ} e′ iff θ_{−}(e, e′) |− θ_{+}(e, e′)

for all e, e′ ∈ E. Now, rather than specifying a particular θ, suppose instead Θ were the set of all such θ’s. Then it is reasonable to assert that e logically entails e′ iff {θ ∈ Θ : e |−_{θ} e′} is a large subset of Θ. Insisting that Θ is the one “large subset of Θ” amounts to a supervaluation approach (van Fraasen [12]). But we might explore other possibilities, subject to minimal conditions such as

(∗) whenever A is a large subset of Θ, every subset B of Θ for which A ⊆ B is also a large subset of Θ.

Then, writing L for the large subsets of Θ, it is natural to extend |− to a relation |−_{L} on E, defined by

e |−_{L} e′ iff {θ ∈ Θ : e |−_{θ} e′} ∈ L

for all e, e′ ∈ E. To guarantee that |−_{L} is the same as |− on Φ, it suffices to require of every θ ∈ Θ that for all φ, ψ ∈ Φ

θ_{−}(φ, ψ) = φ = θ_{+}(ψ, φ) ,

an eminently plausible assumption even if ψ is in E − Φ. That assumption corresponds to clause (12) in Definition D. While the parameters Θ and L are assumed simply to be given, just as a is for Definition D, we may nonetheless investigate how these might relate to (·, ·, ·)_{a}.

As a first attempt, why not take θ_{−}(e, e′) = (⊤, e, e′)_{a} and θ_{+}(e, e′) = (e, e′, ⊤)_{a}? The snag here is that whereas θ_{−}(e, e′) and θ_{+}(e, e′) are assumed to have unambiguous values, neither (⊤, e, e′)_{a} nor (e, e′, ⊤) need be in Φ. (Indeed, the definition of |−_{L} above appeals not to just one θ, but to a collection Θ of these; it is with Θ that (·, ·, ·)_{a} should be related.) So suppose either (⊤, e, e′)_{a} or (e, e′, ⊤)_{a} is not in Φ. We could try to append some expression l to the left of e such that (l, e, e′)_{a} ∈ Φ and (l; e, e′, ⊤)_{a} ∈ Φ, and then set θ_{−}(e, e′) to (l, e, e′)_{a} and θ_{+}(e, e′) to (l; e, e′, ⊤)_{a}. More generally, any number of θ’s might be obtained by attaching expressions simultaneously to the left, right and in between e and e′ so as to totally disambiguate e and e′. As for the family L of large subsets of Θ, that notion might be defined from the preference relations ≺_{a}^{l,r} on E (mentioned in (†) and in the interpretation (11) of •) as follows. Writing ⪯_{a}^{l,r} for the reflexive closure of ≺_{a}^{l,r}, i.e.,

e ⪯_{a}^{l,r} e′ iff e ≺_{a}^{l,r} e′ or e = e′ ,

let L consist of every subset A of Θ such that for every disambiguation, there is a ⪯_{a}^{l,r}-preferred one in A,

A ∈ L iff (∀θ ∈ Θ)(∀e, e′ ∈ E)(∃θ′ ∈ A)
θ′_{−}(e, e′) ⪯_{a}^{⊤,e′} θ_{−}(e, e′) and
θ′_{+}(e, e′) ⪯_{a}^{e,⊤} θ_{+}(e, e′) .

Observe that such an L verifies condition (∗) above, and that the conservative case L = {Θ} of supervaluation arises from the absence of any preference (i.e., for all l, r ∈ E, ≺_{a}^{l,r} is the empty relation ∅). Consequence relations |∼ involving a preference order are familiar in the literature (e.g., Hobbs, Stickel, Appelt and Martin [16] and Beaver [5]), a wide variety of which (considered in Kraus, Lehmann and Magidor [20]) can be characterized by introducing an ambiguous expression c subject to a similar scheme L of preferential contextual disambiguation, with

φ |∼ ψ iff φ; c |−_{L} ψ

for all unambiguous formulas φ, ψ. A precise statement and proof are given in Fernando [11], although much more work remains to be done on extending |∼ to ambiguous expressions.^{7} Suffice it, for now, to say that the rogue expression c represents an indeterminate leap in context (implicated, for example, in presupposition) that can serve as a fix, loosening up the tight constraint imposed on ; by (9).

The passage from a disambiguation strategy and an unambiguous consequence relation |− to some ambiguous consequence relation |−_{L} suggests a logical notion of monotonicity (distinct from the aforementioned operational notions of left and right monotonicity), requiring that for all e, e′ ∈ E,

e |−_{L} e′ implies (∀l ∈ E) l; e |−_{L} e′
and/or (∀r ∈ E) e; r |−_{L} e′ .

Personally, I find the previous operational notions of monotonicity more plausible requirements than a logical one, and see no reason (at the moment) why the slogans “monotonic interpretation” (from Alshawi and Crouch [2]) and “disambiguation as defeasible reasoning” (from Poesio [23]) must be irreconcilable. It is difficult to dispute the non-monotonicity in our everyday reasoning with ambiguous expressions. But, as a design principle, it is sensible to construe the unambiguous character of formulas in Φ as the requirement 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 − Φ. The flaw in this argument is that it may have the absurd(?) consequence that (l, e, r)_{a} ∈ Φ only when e ∈ Φ (the presumption being that ambiguity can never be resolved unambiguously inasmuch as any disambiguation can be reversed with further discourse); however, matters need not get this far, as long as we come to terms with the idea that any fixed disambiguation strategy a is bound to break down on some discourse (contrived pathologically perhaps for that very purpose). In any case, my hope is that the division between operational and logical approaches can serve as a tool for sorting out conflicting intuitions. And while I have no opinion as to how questions of priority and equivalence between operational and logical conceptions should intuitively be resolved, the distinction between them can be characterized quite crisply, I think, in very plain terms. Those terms have to do with how the partiality of disambiguation is formulated — either by delaying disambiguation, as in (11), or (following the time-honored practice of modelling a partial object by the set of its completions) by passing to some set Θ of total disambiguations (not to mention, some notion L of large subset of Θ).

7An essential difference, for instance, is that even the principle (LLE) of left logical equivalence in Kraus, Lehmann and Magidor [20] becomes questionable under a formalization in which disambiguation need not respect truth-conditional equivalence (and the assumption that [[φ]]_{a} = [[φ]] for unambiguous formulas φ must be weakened). On the other hand, lest we think that logic is completely irrelevant to disambiguation, it is perhaps worth citing the Strongest Meaning Hypothesis of Dalrymple, Kanazawa, Mchombo and Peters [6] as an important thesis linking logical entailment to disambiguation.

4. Conclusion

The present paper proceeds from the premiss that ambiguous expressions require disambiguation for an unambiguous interpretation, but that ultimately the essence of ambiguity lies in the variety of notions of disambiguation from which to choose. To analyze that variety, two recipes are provided above, the first of which (in §2) reformulates a partial disambiguation strategy a into a ternary disambiguation function (·, ·, ·)_{a} that

(i) supports an abstract compositional interpretation of expressions on which (·, ·, ·)_{a} is defined,

(ii) provides a natural means in which to state operational constraints on

a, but (iii) need not have anything to do with models or truth (on which a non-

representational semantics is based). Towards a non-representational semantics for ambiguous expressions, the second recipe extends (in §3) an unambiguous consequence relation |− to ambiguous expressions, assuming certain ingredients Θ and L. The problem arises as to how to transform the ingredients for one recipe into ingredients for the other.^{8} Indeed, precisely what ingredients should be used in either recipe is an open matter left for experimentation, the hope being that “good” disambiguation strategies can be identified by studying what these recipes yield separately and, via some transformation between ingredients, jointly. Admittedly, the present work is very programmatic. In its defense, its “definition to theorem” ratio is not quite as bad as it may appear, assuming one takes into account related theorems from Fernando [10, 9, 11], which have not been properly stated above (for the sake of readability).

8We have only touched on one direction above — i.e., from a to Θ, L — but clearly the opposite direction cries out for just as much attention. Such labor will presumably bear fruit when suitable complementary transformations are composed.

Finally, a few closing words about a question, some answer to which the patient reader may well demand.

Why might the constructs •, ; and x =? (analyzed in Definition D) be so special?

From the point of view of logical semantics, it would be natural to investigate a calculus of sequents validating

e_{1}, …, e_{n} |− e′_{1}, …, e′_{m} iff e_{1}; …; e_{n} |− e′_{1} • ⋯ • e′_{m}

(concerning which recall, in §3, (i) the appeal to the relations ≺_{a}^{l,r} interpreting •, for a notion L inducing |−_{L}, and (ii) the use of ; to inject a rogue context c into the antecedent). As for the DRT expression x =?, it is arguably the ultimate underspecification construct, assuming the claim that ambiguity can be characterized uniformly in terms of unresolved variables. Within computational linguistics, this claim has been tested extensively by work on (revised) Quasi Logical Form (QLF, Alshawi and Crouch [2]), and related formalisms (van Genabith and Crouch [13], Pinkal [22]). All that is offered here is a semantics and formal setting, within which to state and study discourse effects on disambiguation.

Acknowledgments

My thanks to Nicholas Asher, Hans Kamp, Peter Krause and Carl Vogel for helpful discussions.

References

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

[2] H. Alshawi and R. Crouch. Monotonic semantic interpretation. In Proc. 30th Annual Meeting of the Association for Computational Linguistics, 1992.

[3] N. Asher and T. Fernando. Labeling representations for effective disambiguation. To be presented in the Second International Workshop on Computational Semantics (IWCS II). Tilburg, The Netherlands, January 1997.

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

[5] David Ian Beaver. Presupposition and assertion in dynamic semantics. Dissertation, University of Edinburgh, 1995.

[6] M. Dalrymple, M. Kanazawa, S. Mchombo, and S. Peters. What do reciprocals mean? In Proc. Fourth Annual Semantics and Linguistic Theory Conference. Cornell University, May 1994.

[7] 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.

[8] Solomon Feferman. A language and axioms for explicit mathematics. In J.N. Crossley, editor, Algebra and Logic, LNM 450. Springer-Verlag, Berlin, 1975.

[9] 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.

[10] Tim Fernando. Ambiguity under changing contexts. Manuscript, 1996. Preliminary version presented in Mathematics of Language 4 (Philadelphia, October 1995), and submitted for publication.

[11] Tim Fernando. Non-monotonic consequences of preferential contextual disambiguation. In P. Dekker and M. Stokhof, editors, Proc. Tenth Amsterdam Colloquium. ILLC, University of Amsterdam, 1996.

[12] B.C. van Fraassen. Presupposition, implication and self-reference. Journal of Philosophy, 65, 1968.

[13] J. van Genabith and R. Crouch. Direct and underspecified interpretations of LFG f-structures. In COLING-96. Copenhagen, 1996.

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

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

[16] J. Hobbs, M. Stickel, D. Appelt, and P. Martin. Interpretation as abduction. Artificial Intelligence, 63, 1993.

[17] J. Jaspars and M. Kameyama. Preferences in dynamic semantics. In P. Dekker and M. Stokhof, editors, Proc. Tenth Amsterdam Colloquium. ILLC, University of Amsterdam, 1996.

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

[19] E. König and U. Reyle. A general reasoning scheme for underspecified representations. Preprint, 1996.

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

[21] Reinhard Muskens. Combining Montague semantics and discourse representation. Linguistics and Philosophy, 19(2), 1996.

[22] Manfred Pinkal. Radical underspecification. In P. Dekker and M. Stokhof, editors, Proc. Tenth Amsterdam Colloquium. ILLC, University of Amsterdam, 1996.

[23] Massimo Poesio. Disambiguation as (defeasible) reasoning with underspecified representations. In P. Dekker and M. Stokhof, editors, Proc. Tenth Amsterdam Colloquium. ILLC, University of Amsterdam, 1996.

[24] Rob A. van der Sandt. Presupposition projection as anaphora resolution. Journal of Semantics, 9(4), 1992.