\underline{\underline{\underline{4}}} Computational foundations for dynamic accounts of presuppositions

1. Introduction

It is one thing to understand a natural language, quite another matter to spell out what it is that is understood (let alone just how that understanding comes about). It is considerably simpler to devise an artificial language of formulas, and to define a semantic function [[·]] specifying the meaning [[φ]] of a formula φ. Of course, the plausibility of such an analysis rests on the extent to which the meaning of a natural language expression e can be characterized as [[φ_{e}]], for some (preferably “natural”) association of formulas φ_{e} with natural language expressions e. The present paper is concerned, more concretely, with analyses of presuppositions by formulas subjected to so-called dynamic semantics, under which the meaning of a formula φ is equated with its context change potential (CCP) — i.e., a binary relation [[φ]] on (the set of) contexts, or states, s and s′ specifying the input/output behavior of φ

(1)  s[[φ]]s′ iff on input s, φ can return output s′ .

A paradigmatic example of dynamic semantics is Discourse Representation Theory (DRT, Kamp and Reyle [13]), central to which is an algorithm constructing discourse representation structures (DRS’s) from syntactic analyses of natural language expressions. That algorithm is studied in a much simplified form below, with both DRS’s and syntactic analyses of natural language expressions replaced by formulas akin to those in first-order logic, following the spirit (but not the letter) of Dynamic Predicate Logic (DPL, Groenendijk and Stokhof [8]). Although DPL departs in significant respects from DRT, much of what follows applies to both DRT and DPL, hence the notation DRT/DPL. By contrast, various analyses of presuppositions based on line (1) above build on semantic structures going beyond that of DRT/DPL, giving rise to the question of the adequacy of DRT/DPL. That question is investigated at length below, alongside the more fundamental problem of computing CCP’s (in accordance with Church’s thesis).

To understand what is going on here, it is useful to ask two simple questions, fleshing out line (1)

(Q1) What is a state s?
(Q2) When does φ define a transition from s

— i.e., when is s in dom([[φ]])?

At its most elementary level, DRT/DPL provides the following answers: a state s is a partial function f : Var ⇁ |M| (called an “Membedding” in DRT, and assumed to be total in DPL) from a fixed set Var of variables to the universe |M| of some first-order model M,

and s ∈ dom([[φ]]) exactly if φ is true (or better — in view of section 5 below —, satisfiable) in s.

Accordingly, the negation ¬φ of a formula φ is analyzed in DRT/DPL as follows

s[[¬φ]]s′ iff s = s′ and s ∉ dom([[φ]]) .

Observe that DRT/DPL negation ¬ is “semantic” insofar as [[¬φ]] depends only on [[φ]]; that is, if [[φ]] = [[ψ]] then [[¬φ]] = [[¬ψ]]. But is the notion of negation used to identify presuppositions semantic (in that same sense)? What is troublesome about presuppositions is that they concern not only what information is conveyed, but also how it is presented, a point driven home to the present author by E. Keenan through the following pair of sentences:

        John is the one linguist who came to the party.
        John is the only linguist who came to the party.

Presuppositions aside, these two sentences would seem to express the same claim (supported, as they are, by exactly the same contexts). But now, to uncover their presuppositions, form their negations by changing “is” to “is not”, and the semantic equivalence breaks down. Evidently, neither this syntactic negation operation nor the extraction of presuppositions can be interpreted semantically.

Alternatively, negation can be “semanticized” (compositionally) by enriching the semantic interpretation of a formula to carry its negation. That is, the syntax/semantics distinction between how information is conveyed (≈ syntax) and what information is presented (≈ semantics) can be blurred by turning a bit of the “how” into “what.” Repackaging an embedding f : Var ⇁ |M| as a world-sequence pair (M, f), Heim [11] and Beaver [1] pass to a notion of state — commonly referred to as an information state — given by a set of world-sequence pairs, allowing not only transitions to the empty set, in cases of falsity, but also the possibility that no output is returned. Staying at the elementary level where states are world-sequence pairs — or wsp’s, for short —, van Eijck [3] introduces transitions to an “error state”, called ϵ, in cases of presupposition failure. In terms of questions (Q1) and (Q2) above, the situation can be described as follows

(Q1)  (Q2)
DRT/DPL wsp (M, f)  satisfiability
Heim/Beaver set of wsp’s  presupposition success
van Eijck  wsp or ϵ satisfiability or presup failure

The “positive” content (+) of a formula can be distinguished from its “negative” content (−) according to

(+)  (−)
Heim/Beaver transition to non-empty set transition to ∅
van Eijck  transition to non-ϵ-state no transition

An explicit separation between positive and negative components is provided by the transition/anti-transition pairs ([[φ]]^{+}, [[φ]]^{−}) of Krahmer [15], where ideas from ordinary 3-valued logic are adapted to DPL. Now, the present work proposes further to restore the syntax-semantics distinction by defining translations pos and neg between formulas such that [[φ]]^{+} = [[pos(φ)]] and [[φ]]^{−} = [[neg(φ)]] under the usual DRT/DPL interpretation [[·]], and characterizing the presuppositions pres(φ) of a formula φ as pos(φ) ∨ neg(φ). That is, rather than semanticizing presuppositions by changing the answers of DRT/DPL to (Q1) and (Q2), Keenan’s intuition is developed via syntactic manipulations that keep the DRT/DPL semantic framework largely intact. Thus, van Eijck’s introduction of an error state into the semantic framework can be avoided by “syntacticizing” φ-transitions to ϵ as ¬pres(φ). It is important here not to confuse DRT/DPL negation ¬ with syntactic translations neg used to test presuppositions (of which there might be a multitude, in contrast to the single semantic notion ¬ of negation). A common semantic basis would facilitate a comparison of different accounts of presuppositions, including van der Sandt [18]. A reduction to DRT, in particular, is of both scientific and practical interest, in view of the amount of extant work using, analyzing and implementing DRT. There is also the broader and, as it turns out, related question of computing CCP’s, which is taken up in section 2. The central thrust of the present work is to formulate dynamic accounts of presuppositions within a computational semantic framework by introducing on top of that framework translations that are naturally regarded as pragmatic constructs.^{1} Such translations are studied in section 3, and their connection with pragmatic approaches to presuppositions considered briefly in section 4, where the main problem is put to be that of choosing an appropriate translation.

Turning finally to the logical motivation for adopting dynamic semantics, it must be conceded that there is, at the surface, nothing particularly dynamic about characterizing presupposition as the disjunction of positive and negative components. That is not to say, however, that the shift from truth to change (as the basic semantic concept) is without consequence. In particular, that shift suggests presentations of pos(φ) as presupposition-assertion pairs (pres(φ), as(φ)), complementing the reduction of pres(φ) to pos(φ) ∨ neg(φ). These presentations are related in section 5 to the broader conception of discourse interpretation as a “dynamic” construction of contexts, rather than a “static” evaluation of truth against a fixed context (a conception that, in turn, supports an anaphoric analysis of presuppositions; e.g., van der Sandt [18]).

1That is, the object of the present paper is to supply computational foundations (in the sense described in section 2) for CCP models of presuppositions, and not (so much)

to expand their linguistic coverage (insofar as such coverage is deemed independent of computational considerations).

2. Computing context change potentials

To start out, let us fix a signature (or vocabulary) L, a countable set Var of variables, and a sufficiently large set M of L-models (e.g., those whose universe is a set of ordinals less than the cardinality of the set of L-formulas). Let WSP be the set of wsp’s (M, f) where M ∈ M and f is a partial function from Var to the universe of M. Let us also fix a set Φ of formulas — for example (but not necessarily) DRS’s — that will be interpreted by binary relations called CCP’s. To avoid confusing the different CCP’s that will be considered, let us write P (φ) for the CCP of φ ∈ Φ relative to wsp’s,

P (φ) ⊆ WSP × WSP .

Let us assume also that

dom(P (φ)) = {(M, f) ∈ WSP : φ is satisfiable in (M, f)} ,

for some notion of “satisfiability” that can be linked, for example, to Tarski’s definition of satisfaction ⊧ as follows. A first-order L-formula χ is a characteristic formula of φ if for every wsp (M, f) and every L-model M_{0},

(M_{0}, ∅) P (φ) (M, f) iff M = M_{0} and

dom(f) = FVAR(χ) and M ⊧ χ[f]

where FVAR(χ) is the set of free variables of χ. Now, to try out the computational demands of P, let L = { ˙+, ˙×, ˙0, ˙1} be a language for arithmetic, and N be its standard model ⟨{0, 1, 2, … }, +, ×, 0, 1⟩. Note that every first-order L-sentence (without a free variable) is the characteristic formula of some DRS φ.^{2} It follows immediately that for the collection Φ of DRSs, the set

{φ ∈ Φ : (N, ∅) ∈ dom(P (φ))}

is non-arithmetic — i.e., computationally hopeless. That is to say, the notion from Quantified Dynamic Logic (see, e.g., Harel [10], where particular attention is given to the model N) of computing over a fixed first-order model cannot be transferred to DRT/DPL. The culprit is the DRT/DPL notion of negation ¬, which is interpreted by P as a test for the complement of the halting problem

P (¬φ) = {(s, s) : s ∈ WSP − dom(P (φ))} .

(In dynamic logic, ¬φ can be equated with [φ]⊥?, where [φ] is the box modality labeled by φ, and ⊥ is some unsatisfiable statement; but to say that [φ]⊥? is a program is to deny that every program can be computed.)

2This is worked out in detail in Fernando [4], which expands considerably on the present section, disputing widespread claims that dynamic semantics is “computational” because its formulas are programs [sic] of dynamic logic.

To interpret the formulas in a computationally meaningful manner, we must pass from a fixed (albeit arbitrary) choice of a model to a sufficiently large collection of models, moving from a computationally intractable notion of satisfaction (relative say to N) to a notion of semantic validity (involving say countable models of Peano arithmetic) amenable (by Gödel’s completeness theorem) to syntactic manipulations. This passage is effected by the classic “subset construction” from automata theory (e.g., Hopcroft and Ullman [12]) that determinizes non-deterministic (finite) automata. An operation, call it D, can be extracted from that construction that (more generally) turns a binary relation R on any set S to a function D[R] defined on subsets σ of S by

D[R](σ) = {s′ : (∃s ∈ σ) sRs′} .

Rather than studying arbitrary sets of wsp’s, let us concentrate on certain “accessible” sets, starting with the initial information state

σ_{∘} = {(M, ∅) : M ∈ M} .

Observe that σ_{∘} has zero information content insofar as no model in M has been eliminated, and no variable has been initialized. The set Acc of accessible information states is then the smallest set Σ of information states including σ_{∘}, and closed under the rule

\frac{σ ∈ Σ}{D[P (φ)](σ) ∈ Σ} φ ∈ Φ , D[P (φ)](σ) ≠ ∅ .

Having quantified out the choice of a model in an an accessible information state, we are now in a position to characterize, in purely syntactic terms, the restriction of D[P (φ)] to Acc, for every φ ∈ Φ. Let Φ_{⊥} be a set of formulas that are said to be absurd, and let & be a binary connective on Φ that merges formulas. For every φ ∈ Φ, define the CCP →^{φ} ⊆ Φ × Φ by

ψ →^{φ} ψ′ iff ψ′ = ψ&φ and ψ′ ∉ Φ_{⊥} .

(Note that each CCP →^{φ} is a partial function.) Call a formula φ trace equivalent to an information state σ, denoted φ ∼ σ, if for every finite sequence φ_{1}, …, φ_{n} of formulas,

φ ∈ dom(→^{φ_{1}} ∘ ⋯ ∘ →^{φ_{n}}) iff D[P (φ_{n})](⋯ (D[P (φ_{1})](σ)) ⋯)
≠ ∅ .

Also, for every φ ∈ Φ, let σ_{φ} abbreviate D[P (φ)](σ_{∘}).

Equivalence Lemma. Assume that

Φ_{⊥} = {φ ∈ Φ : σ_{φ} = ∅} ,

and that P interprets & as relational composition ∘ — for all φ, φ′ ∈ Φ,

P (φ&φ′) = P (φ) ∘ P (φ′) .

Then for every φ ∈ Φ, φ ∼ σ_{φ}.

Because →^{φ} and D[P (φ)] (restricted to non-empty information states) are deterministic relations (for every φ ∈ Φ), trace equivalence is the same as the equivalence induced (maximally) by the notion of a bisimulation (Park [16]). This is of some interest in that, in general, the former is commonly accepted as the coarsest notion of equivalence on states, whereas the latter is taken to be the finest. For both notions of equivalence, one must be careful about transformations that produce transitions when before there were none — e.g., D[R]-transitions to ∅. Hence, D[P (φ)] is restricted to non-empty information states in the definition of trace equivalence.

Confining our attention to states in the CCP’s →^{φ}, define an equivalence relation \underline{↔} on Φ by

φ \underline{↔} ψ iff (∀φ′ ∈ Φ) (φ&φ′ ∈ Φ_{⊥} iff ψ&φ′ ∈ Φ_{⊥})

(which corresponds to bisimulation equivalence over the →^{φ}’s).

Equivalence Theorem. If, in addition to the assumptions from the previous lemma, every formula has a characteristic formula, then not only is φ ∼ σ_{φ} for every φ ∈ Φ, but also

(i) for all φ and φ′ ∈ Φ,

φ \underline{↔} φ′ iff σ_{φ} = σ_{φ′} ,

and (ii) both \underline{↔} and Φ_{⊥} are recursively enumerable.

Part (i) of the theorem says that the restriction of D[P (φ)]’s to non-empty accessible information states is a strongly extensional quotient of the CCP’s →^{φ} (meaning roughly that it abstracts out all syntactic details in →^{φ}). Formulating an l-transition from φ to ψ as a triple (φ, l, ψ), part (ii) provides a recursively enumerable reformulation of →^{φ}-transitions as the set

{(ψ, φ, ψ&φ) : ψ, φ ∈ Φ} ∪ {(φ, ⊥, φ) : φ ∈ Φ_{⊥}}

of transitions, bisimulation equivalence over which is given (also) by \underline{↔}. In other words, choosing contexts (on which CCP’s operate) to be information states, as opposed to formulas, involves a trade-off between the canonicity specified by part (i), and the recursive enumerability in part (ii). Part (ii) is proved by appealing to Gödel’s completeness theorem to conclude that

φ \underline{↔} φ′ iff |− (∀\overline{x}) χ_{φ} ≡ χ_{φ′}
φ ∈ Φ_{⊥} iff |− ¬∃\overline{x}χ_{φ}

for all φ and φ′ ∈ Φ, with characteristic formulas χ_{φ} and χ_{φ′}, respectively.

3. Translating transitions and anti-transitions

Turning to presuppositions, let us consider the notion that the presuppositions pres(φ) of a formula φ are determined by the domain of its CCP [[φ]]

(2)  pres(φ) ≈ dom([[φ]]) .

Now what could [[φ]] be? Certainly, it cannot be P (φ), as the domain of P (φ) is too small, consisting only of wsp’s at which φ is satisfiable. Intuitively, the presuppositions of φ can be met also at states where φ is unsatisfiable. Applying the subset construction D to P (φ), it is tempting to say that the presuppositions of φ can hold at an information state σ for which D[P (φ)](σ) = ∅. Of course, the problem now in identifying D[P (φ)] with [[φ]] in (2) is that the domain of D[P (φ)] is too big, being (as it is) the full power set of WSP. Accordingly, Heim [11] and Beaver [1] revise D[P (φ)] into a partial function, thereby allowing for presupposition failure, but also leaving unexplained the intuition (on which they build) that

an information state is the set of wsp’s possible under it

(as partiality blocks the reduction via D of CCP’s to transitions between wsp’s). Be that as it may, note that a transition from an information state σ to the empty set is a “negative” transition inasmuch as it arises from the failure of any wsp in σ to return an output — failures that can be put positively as successful applications of ¬ to the wsp’s in σ. Of course, this cannot be the whole story of transitions between wsp’s, as an explanation of presupposition failure is missing. Enter van Eijck [3]’s error state ϵ, from which presumably the Heim/Beaver CCP’s between information states can be reconstructed along the lines of D. I have yet to see such a reconstruction worked out rigorously, nor am I particularly keen about carrying it out myself, as I do not see that much can be gained in explaining an error through an error. (Are errors meant to be introduced or to be eliminated?) It is far preferable, I believe, to provide an analysis of presupposition errors without building an error state into the stock of semantic primitives, retaining instead the distinction (going back to Keenan’s forementioned insight) between what information is presented and how it is conveyed.

Toward that end, I propose that the characterization (2) of pres(φ) be revised to

pres(φ) ≈ pos(φ) ∨ neg(φ)

for certain functions pos and neg on formulas that are subjected to the usual semantics P (which, in particular, interprets disjunction ∨ as

P (ψ ∨ ψ′) = {(s, s) : s ∈ dom(P (ψ) ∪ P (ψ′))}

for all ψ and ψ′ ∈ Φ).^{3} The translations pos and neg (not to be confused with ¬) are not meant to be carved into stone in the same way that P (or ¬) is, although the reader is certainly free to do as she pleases. Putting off to the next section what exactly I mean by not carving pos and neg into stone, let me concede, for now, that she can pass to the transition/anti-transition pairs [[φ]]^{+}, [[φ]]^{−} of Krahmer [15], by composing the semantics P with the translations pos and neg, respectively. That is to say, she can ride roughshod over the what/how (semantics/syntax) distinction that I have taken pains to maintain, by semanticizing the whole business. Evidently, there is no point in being too dogmatic about a distinction that is so easily obliterated. On the other hand, the matter can be turned on its head by asking if transition/antitransition pairs [[φ]]^{+}, [[φ]]^{−} admit a decomposition as P (pos(φ)), P (neg(φ)).

3Whereas the introduction of a translation neg has been motivated above by the need to consider “negative” transitions, the appearance of pos (at this point) may seem a bit mysterious. Suffice it to say that for reasons of symmetry that should become clear in the example below, it is useful to have a translation pos that differs from the identity function.

With this question in mind, note that the following (semantic) operations on pairs (a, b) are basic to the conception of the meaning of a formula as a positive/negative pair

POS(a, b) = a
NEG(a, b) = b
∼(a, b) = (b, a) .

The present proposal is to formulate these operations on sem(φ) = ([[φ]]^{+}, [[φ]]^{−}) through translations pos, neg, and − (respectively) such that

POS(sem(φ)) = P (pos(φ))
NEG(sem(φ)) = P (neg(φ))
∼sem(φ) = sem(−φ) ,

preserving the DRT/DPL system P of CCP’s. Only the translations pos and − need be specified, if it is assumed (as it will) that neg is the composition of the two translations

neg(φ) = pos(−φ) .

The literal (i.e., syntactic) equality

−−φ = φ

can then be arranged by defining a function ˆ· mapping n-ary relation symbols R to n-ary relation symbols R̂, and n-ary logical connectives α to n-ary logical connectives α̂ such that

ˆR̂ = R

and

ˆα̂ = α .

To construct such a map ˆ·, it may be necessary to throw in fresh relation symbols and logical connectives, and stipulate that

−R(\overline{t}) = R̂(\overline{t})

and

−α(φ_{1}, …, φ_{n}) = α̂(φ̃_{1}, …, φ̃_{n}) ,

where φ̃_{i} is either φ_{i} or −φ_{i} (simplifying the notation somewhat, by suppressing the subscripts α and i on the tilde ˜·). The choice between setting φ̃_{i} to φ_{i} or to −φ_{i} depends on whether the ith argument occurs “negatively” or “positively,” as will be illustrated presently.

Example. A familiar practice in 3-valued logic is to stipulate that conjunction ∧ and disjunction ∨ form a dual pair according to De Morgan’s laws

−(φ ∧ ψ) = −φ ∨ −ψ
−(φ ∨ ψ) = −φ ∧ −ψ .

Note that “dynamic” conjunction & (interpreted by relational composition) should be distinguished from ∧, for which let us agree that

pos(φ ∧ ψ) = ¬(¬pos(φ) ∨ ¬pos(ψ)) .

Assuming that P interprets implication ⊃ by^{4}

P (φ ⊃ ψ) = {(s, s) : s ∈ WSP and
{s′ : s P (φ) s′} ⊆ dom(P (ψ))} ,

define

−(φ&ψ) = φ ⊃ −ψ
−(φ ⊃ ψ) = φ & − ψ

(noting that in φ ⊃ ψ, φ occurs negatively, while ψ occurs positively), and

pos(φ&ψ) = pos(φ) & pos(ψ)
pos(φ ∨ ψ) = pos(φ) ∨ pos(ψ)
pos(φ ⊃ ψ) = pres(φ) & (pos(φ) ⊃ pos(ψ)) .

The preceding is largely consistent with section 6 of Krahmer [15] (devised in collaboration with R. Muskens), which also treats random assignments x :=?, a form of negation, and a certain presupposition construct φ_{⟨π⟩}, all of which can be brought within the present framework.^{5}

φ&ψ as φ; ψ
φ ∨ ψ as ¬¬(φ + ψ)
φ ⊃ ψ as ¬(φ; ¬ψ)
pos(A) = A  for atomic formulas A
pos(x :=?) = ∃x x = x
pos(φ_{⟨π⟩}) = pos(π) & pos(φ) .

4The reader familiar with dynamic logic might regard formulas as [sic] programs and rewrite where, as previously noted, ¬φ is the test [φ]⊥?. Although the connectives ∨ and ⊃ can be defined from & and ¬ (which can, in turn, be given as · ⊃ ⊥), certain “dualities” that are presently of interest are best brought out by taking ∨ and ⊃ also to be primitive.

5A minor point of departure is that [[φ ⊃ ψ]]^{−} in section 6 of Krahmer [15] is the static projection ¬¬neg(φ ⊃ ψ) of the present interpretation. Otherwise, put in terms of our present approach, the proposal there is that

4. Choosing translations: a pragmatic turn

Characterizing the presuppositions pres(φ) of a formula φ as pos(φ) ∨ neg(φ), for translations pos and neg obtained by extending the extension/antiextension pairs familiar from 3-valued logic to logical connectives may well strike the reader as an exercise in a semantic approach to presuppositions. (A “semantic” approach is understood here to be one based on Strawson’s reduction of presuppositions to conditions for truth or falsity — i.e., bivalence.) This impression is incorrect on two counts.

(i) The semantic values assigned to formulas are not truth values. Indeed, reference to truth has, up to this point, been carefully avoided (except for the use of the term “true” in the introduction, which was quickly changed to “satisfiable”).

(ii) Were I compelled to describe the approach to presuppositions I intend

to push as either semantic or pragmatic, I would choose the latter label. Let us take up these two points in turn.

With regard to (i), note that although ideas from 3-valued logic are employed in the previous section, the following assignment of truth values need not yield a 3-valued logic

φ is true at s iff s ∈ dom(P (pos(φ)))
φ is false at s iff s ∈ dom(P (neg(φ)))
φ is undefined at s  otherwise .

Not only does this definition fail to rule out the possibility of a fourth truth value (in case φ is both true and false at s), it can be ill-behaved even over the two ordinary truth values, as illustrated by the following case in DPL. Let M be a first-order model that interprets a unary relation symbol R by a disjoint extension/anti-extension pair such that neither set is empty, and let f be an embedding into M that maps the variable x to the anti-extension of R. Then R(x) is false at f, ∃x R(x) is true at f, but (∃x R(x)) & R(x) is true at f, which is to say that a false formula can become true if (pre- )conjoined with a true formula. (Of course, there will also be cases where a

−(x :=?) = ? =: x
−(? =: x) = x :=? ,
−(φ_{⟨π⟩}) = _{[π]} − φ
−(_{[π]}φ) = (−φ)_{⟨π⟩} ,
pos(_{[π]}φ) = (pos(π) ⊃ pos(φ)) & pos(π) & pos(φ) .

Krahmer’s negation can be defined away through the translation − by introducing constructs dual to random assignment and to the presupposition operator and subject to

pos(? =: x) = ⊥ (where P (⊥) = ∅)

true formula conjoined with a false formula is false.) The simple lesson here is that formulas are interpreted semantically as binary relations, and some thought needs to be invested to derive a natural notion of truth from a relational interpretation. We will take up this challenge in the next section, but first, onto point (ii) and the pragmatic character of presuppositions.

I have already mentioned that the translations pos and neg should not be accorded the same status as P or ¬. Following up on Keenan’s insight, P and ¬ concern what information is presented, whereas pos and neg have to do with how it is conveyed. True, this distinction can be rubbed out by the compositions P ∘ pos and P ∘ neg, semanticizing everything to transition/antitransition pairs. But I fail to see what is achieved by mixing up what with how, particularly when firm answers can be supplied to the former, by taking a softer stance toward the latter. Take, for example, a conditional if A then B. It is not at all clear how to characterize its presuppositions uniformly for all A’s and B’s. Although it is commonly taken for granted in semantic approaches to presupposition (including dynamic ones) that the conditional should inherit the presuppositions of its antecedent A, there are troublesome sentences such as

               If Erwin realizes the cat is dead,
                      then the cat is dead

that would suggest otherwise.^{6} And the situation does not get any easier with the presuppositions of the consequent B, the study of which branches off to “strong” or “weak” presuppositions (e.g., Krahmer [15]), and “global” or “local” or “intermediate accomodation” (e.g., van der Sandt [18]).

Conceptually, the problem is that, as Karttunen [14] puts it, “ordinary discourse is not always fully explicit”

People do make leaps and shortcuts by using sentences whose presuppositions are not satisfied in the conversational context. This is the rule rather than the exception, and we should not base our notion of presupposition on the false premiss that it does not or should not happen. But granting that ordinary discourse is not always fully explicit in the above sense, I think we can maintain that a sentence is always taken to be an increment to a context that satisfies its presuppositions. [p. 191, italics added]

That is, a natural language expression is often ambiguous between different formulations. The most plausible formulation may depend on any number of considerations, including the “conversational context.” Now, a discoursebased account of natural language, such as DRT, differs from a purely sentencebased one by incorporating the conversational context within the representation of the discourse. In particular, building on the system of CCP’s →^{φ} described in section 2, the conversational context can be identified with a formula that not only can be fed as an input to a CCP, but itself defines a CCP (making it both computationally amenable and computationally active). Thus, Beaver [1]’s picture (intended to model global accomodation) of a single formula that takes as input a preference ordering on information states can be “dualized” into a picture of a single input fed to a preference ordering on formulas. The latter preference ordering reflects ambiguity, and gives rise, in turn, to the sort of inputs Beaver considers. Moreover, for some DRS’s φ and φ′, merging & is commutative

6I am indebted to Robert van Rooy for bringing such examples (well-known to proponents of pragmatic approaches to presupposition) to my attention.

φ & φ′ = φ′ & φ .

To be more precise, a DRS can be understood as a pair (U, C) consisting of a set U of variables (or discourse markers) and a set C of conditions (that are generated simultaneoulsy with DRS’s). The CCP P (U, C) of a DRS (U, C) is given on wsp’s (M, f) and (N, g) by

(M, f) P (U, C) (N, g) iff M = N and f ⊆ g and

dom(g) = dom(f) ∪ U and each γ ∈ C is verified by (M, g) ,

for some notion of verification defined simultaneously with P. Now, the point is that, modulo pesky variable conflicts that can often be overcome,^{7}

(3)  P (U, C) ∘ P (U′, C′) ≈ P (U ∪ U′, C ∪ C′) .

In cases where (3) can be established, the commutativity of ∪ allows the input DRS (U, C) in (3) to be swapped with the updating DRS (U′, C′).

5. Dynamics and disjunction reconsidered

Looking more closely at Karttunen [14]’s claim that a statement can always be “taken to be an increment to a context that satisfies its presuppositions,” two dimensions of information growth can be discerned in the CCP of a DRS (U, C):

(i) an expansive potential given by U (initializing variables in U), and (ii) an eliminative potential given by C (eliminating contexts that fail to

verify a condition in C). Now, suppose we decomposed the positive transitions pos(φ) of φ into a presuppositional component pres(φ) followed by the remnant of pos(φ), call it as(φ) (for assertion),

pos(φ) = pres(φ) & as(φ) .

Assuming pos(φ) is the DRS (U, C), a simple-minded parallel to the normal form

P (U, C) = P (U, ∅) ∘ P (∅, C)

7A crucial advantage here of DRT over DPL is that in DRT a variable x is assigned a random value iff x is uninitialized.

would shove all expansive growth P (U, ∅) to the presuppositional component pres(φ), leaving the non-presuppositional component as(φ) a purely eliminative character (i.e., making Karttunen [14]’s “increment to a context that satisfies its presuppositions” exclusively eliminative). In such a case, P (¬¬as(φ)) = P (as(φ)) and we might expect to reduce the negation translation neg to DRT/DPL ¬ as follows

neg(φ) = pres(φ) & ¬as(φ) .

But if pres(φ) is to have expansive potential, the characterization pres(φ) = pos(φ) ∨ neg(φ) must be modified, as a disjunction ψ ∨ ψ′ can never expand a wsp:

s P (ψ ∨ ψ′) s′ implies s = s′ .

A simple solution is to replace ∨ by non-deterministic choice +, interpreted as union,

s P (ψ + ψ′) s′ iff s P (ψ) s′ or s P (ψ′) s′ ,

reformulating pres(φ) as pos(φ) + neg(φ), and setting as(φ) to pres(φ) ⊃ pos(φ). This time, however, pres(φ) goes too far, trivializing the non-presup-positional component as(φ). The appropriate disjunction connecting pos(φ) with neg(φ) to yield pres(φ) probably lies somewhere between ∨ and +.

The decomposition of P (U, C) into an expansive component P (U, ∅) followed by an eliminative part P (∅, C) runs parallel also to a Henkin-style proof of Gödel’s completeness theorem, in which a theory is expanded with Henkin witnesses, before it is turned eliminatively to a maximally consistent set. This suggests a view of discourse interpretation as a construction of contexts, with truth derived from change by the equivalence

(4)  φ is true at s iff φ holds at every completion of s .

The equivalence (4) is bound to remind the reader familiar with van Fraassen [7] of supervaluations. The approach I have in mind, however, concentrates on gaps arising from uninitialized variables, rather than those between nonexhaustive extensions and anti-extensions (of, for example, presuppositional verbs such as regret — which arguably ought not to be closed).^{8} To establish (4), it is not enough to equate the completion of a wsp (M, f) with some wsp (M, g), where g is an arbitrary total function extending f. All existential truths in M must be witnessed by g, and, to take an extreme case, a constant function g would witness very few such truths. In the terminology of Boolean-valued semantics, a first-order model cannot be formed simply from an ultrafilter over a Lindenbaum algebra of first-order formulas; the ultrafilter must be generic. For (M, g) to be a completion of (M, f), g should not only extend f, but also be defined, when possible, on variables with conditions attached to them. Such conditions make these variables similar to Henkin witnesses, or to Hilbert’s ϵ-terms. A basic difference here, however, is that these variables must remain uninitialized if the conditions cannot be met. In this respect, they are closer to restricted parameters of situation theory (e.g., Cooper [2]). The precise details are somewhat involved, and form, on their own, an entire paper, the results of which I have space only to summarize. Relative to the partial order ⊑ given on wsp’s (M, f) and (N, g) by

8Although I cannot claim to understand the matter fully, it seems to me that the move made in this section from, on the one hand, pres(φ) = pos(φ) ∨ neg(φ) and extension/antiextension pairs to, on the other hand, pos(φ) = pres(φ) & as(φ) and anaphoric/existential complications is very much in the spirit of the 2-dimensional approach to presuppositions described in van Rooy [17].

(M, f) ⊑ (N, g) iff M = N and f ⊆ g ,

truth is defined by a so-called double intuitionistic negation translation

φ is true at s iff (∀s′ ⊒ s)(∃s′′ ⊒ s′) s′′ ∈ dom(P (φ)) .

In addition to making (4) precise, Fernando [5] establishes the following results.

(i) Recalling that acceptance in Veltman [19] is given by the set fix(P (φ)) of fixed points of P (φ), whereas acceptability amounts to dom(P (φ)), the double negation translation makes acceptance acceptable insofar as

(∀s′ ⊒ s)(∃s′′ ⊒ s′) s′′ ∈ fix(P (φ)) iff
(∀s′ ⊒ s)(∃s′′ ⊒ s′) s′′ ∈ dom(P (φ)) .

(ii) The resulting notion of truth is not only compositional, but also Boolean-

valued. (iii) The double intuitionistic negation translation can be applied to infor-

mation states, under the so-called Smyth pre-order ⊑_{Sm},

U ⊑_{Sm} U′ iff (∀s′ ∈ U′)(∃s ∈ U) s ⊑ s′ ,

so that

(∀U′ ⊒_{Sm} U)(∃U′′ ⊒_{Sm} U′) U′′ ∈ dom(D[P (φ)]) iff

(∀s ∈ U) φ is true at s .

6. Conclusion

Having equated the presuppositions pres(φ) of a formula φ with a disjunction pos(φ) or neg(φ), we have left open, for pragmatic analysis, just what pos, neg and or are. The following (minimal) assumptions have been studied above

neg(φ) = pos(−φ)
dom(P (φ or ψ)) = dom(P (φ) ∪ P (ψ)) ,

where − is a function swapping extensions with anti-extensions, and P is the DRT/DPL semantic map interpreting a formula φ as a CCP P (φ) between world-sequence pairs. The problem of computing P (φ) was taken up in section 2, while guidelines for defining − were suggested in section 3. The last two sections examined notions of truth and context, complementing the reduction of pres(φ) to pos(φ) or neg(φ) with a decomposition of pos(φ) into presuppositional and non-presuppositional components, pres(φ) & as(φ). A comparison of that decomposition with the initialize-and-then-test interpretation of a DRS suggests a “dynamic” re-interpretation of or, giving pres(φ) expansive potential (i.e., allowing P (pres(φ)) to return an output different from its input). In particular, if the non-presuppositional remnant as(φ) is purely eliminative — i.e., P (¬¬as(φ)) = P (as(φ)) —, then we can expect to reduce neg(φ) to pres(φ) & ¬as(φ). But, as with pos and neg, it is not at all clear what the right notion of disjunction is. This is hardly surprising, given the various notions of presuppositions and proposals to accomodate them.

Analyzing presuppositions is no doubt a huge problem, a basic question concerning which is how to divide labor on it in a fruitful manner. Rather than espouse a single notion of presupposition, different notions can be formulated above through pragmatic translations between formulas that are eventually given a DRT/DPL semantics P. The scope of this semantics can be expanded by introducing abstract entities into the worlds. Examples of such entities include proposition-like objects of regret, an “external” analysis of which (Veltman [19]) is linked to presuppositions in Beaver [1]. I close with some words about these developments (i.e., Veltman [19], Groenendijk, Stokhof and Veltman [9], Beaver [1]), as these pose serious problems for the computational foundations supplied above by questioning the adequacy of CCP’s P (φ) defined on wsp’s for analyzing might φ and presuppositions. Squaring the intuition pres(φ) ≈ dom([[φ]]) with a semantics based on P has already been taken up in section 3 (the trouble with existential quantification that Heim [11] has with “a fat man pushing his bicycle” being an artifact of defining CCP’s on information states, rather than on wsp’s). As for might φ, the solution I propose is to introduce formulas as objects in models — providing, as it were, an internal notion of formula, in contrast to the external (metatheoretic) formulas on which Veltman [19] defines the semantics of might φ. A fixed distinguished variable x̂ ranging over internal formulas is designated to keep track of updates, using programs of the form^{9}

record(φ) = if x̂ is uninitialized then x̂ := φ
else x̂ := x̂&φ .

The translation pos is defined in the obvious way by inserting record(φ), the crucial clause being for formulas might φ, which are analyzed through a consistency check on x̂. Adding a unary relation symbol Con to the underlying signature (or vocabulary) of the models in wsp’s, set

pos(might φ) = ¬¬(record(φ) & Con(x̂))
f&φ(x̂) = \{ \begin{matrix}φ & if x̂ ∉ dom(f) \\ f(x̂)&φ & otherwise. \end{matrix}

9That is,

P (record(φ)) = {((M, f), (M, f&φ)) : (M, f) ∈ WSP} with f&φ equal to f except on x̂, where

where the double DRT/DPL negation prefix suppresses the dynamic effects of record(φ). The translation neg is defined as before to be the composition of pos with −, where − is extended to might φ by introducing a dual connective must

−might φ = must(−φ)
−must φ = might(−φ) ,

with pos(must φ) obtained by pushing one of the negations in pos(might φ) through record(φ)

pos(must φ) = ¬(record(−φ) & Con(x̂)) .

Now, returning to the predicate Con behind might, one can show that if we insist that Con always be interpreted in the external sense corresponding to Veltman [19], then the set Φ_{⊥} of absurd formulas (as defined in section 2) cannot be recursively enumerable. Indeed iterated applications of might (alongside quantification) would reach arbitrary heights of the arithmetic hierarchy, leading to ω-logic (Fernando [6]).

Acknowledgments. My thanks to D. Beaver, S. Berman, H. Kamp, E. Keenan, E. Krahmer, P. Krause and R. van Rooy for helpful discussions on this subject.

References

[1] David Ian Beaver. What comes first in dynamic semantics. Dissertation, University of Edinburgh, 1994.

[2] Robin Cooper. Situation theoretic discourse representation theory. Manuscript, HCRC, Edinburgh, 1992.

[3] Jan van Eijck. Presuppositions and dynamic logic. In M. Kanazawa, C. Piñon, and H. de Swart, editors, Papers from the Second CSLI Workshop on Logic, Language and Computation, June 1993. CSLI Lecture Notes, to appear.

[4] Tim Fernando. What is a DRS? In R. Cooper and J. Groenendijk, editors, Integrating Semantic Theories II. Dyana deliverable R2.1.B, 1994. Presented in a Computational Semantics workshop at Tilburg (December 1994).

[5] Tim Fernando. A persistent notion of truth in dynamic semantics. In D. Westerståhl and J. Seligman, editors, Language, Logic and Computation: The 1994 Moraga Proceedings. CSLI, Stanford, To appear.

[6] Tim Fernando. It might change. A reply to Groenendijk, Stokhof and Veltman’s “This might be it”, Unfinished manuscript.

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

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

[9] J. Groenendijk, M. Stokhof, and F. Veltman. This might be it. In D. Westerståhl and J. Seligman, editors, Language, Logic and Computation: The 1994 Moraga Proceedings. CSLI, Stanford, To appear. Also appears in Dyana deliverable R2.1.B, Integrating Semantic Theories II , (R. Cooper and J. Groenendijk, editors), 1994.

[10] David Harel. Dynamic logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic, volume 2. Dordrecht: Reidel, 1984.

[11] Irene Heim. On the projection problem for presuppositions. In M. Barlow, D.P. Flickinger, and M.T. Westcoat, editors, Proc. West Coast Conference on Formal Linguistics, volume 2. Stanford Linguistics Association, California, 1983.

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

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

[14] Lauri Karttunen. Presupposition and linguistic context. Theoretical Linguistics, pages 181–194, 1973.

[15] Emiel Krahmer. Partiality and dynamics: theory and applications. In Proc. Ninth Amsterdam Colloquium. ILLC, University of Amsterdam, 1994.

[16] David Park. Concurrency and automata on infinite sequences. In P. Deussen, editor, Proc. 5th GI Conference, LNCS 104. Springer-Verlag, Berlin, 1981.

[17] Robert van Rooy. A two-dimensional account of presuppositions in quantified contexts, 1995. Manuscript, University of Stuttgart.

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

[19] Frank Veltman. Defaults in update semantics. In H. Kamp, editor, Conditionals, Defaults and Belief Revision. Edinburgh, Dyana deliverable R2.5.A, 1990.

72 Tim Fernando