\underline{\underline{\underline{1}}} Generalized quantifiers as second-order programs — “dynamically” speaking, naturally

Abstract. Generalized quantifiers (understood as functions Q mapping a set M to a binary relation Q_{M} on Pow(M)) are analyzed within the so-called “dynamic” approach to natural language semantics. Under that approach, the meaning of a formula is taken to be the set of input/output transitions it induces, according to a particular translation into programs from some formalism, such as that of (quantified) dynamic logic. The concrete problem addressed here is that variables bound by generalized quantifiers must introduce discourse markers for pronouns (that are typically plural). The solution adopted builds heavily on the “duality” between nondeterminism and parallelism by interpreting programs as binary relations on non-empty subsets of states from dynamic logic, thereby accomodating the conjunctive branching in and-or computation graphs (which can then be weakened relative to a generalized quantifier). (The distinction between definite and indefinite noun phrases is linked to that between deterministic and non-deterministic programs.) The underlying notion of computation is argued to require a global (as opposed to a local) interpretation, complementing the uniformity in a generalized quantifier. The subsets of interest are hypothesized to have a “determinate” character (i.e., to be first-order definable), in accordance with so-called E-type pronouns. An alternative “indeterminate” reading is also formulated within the framework, as are readings that are weak or strong, and distributive or collective.

Introduction

An approach to natural language semantics that has attracted, and continues to attract, a good deal of attention is Discourse Representation Theory (DRT), initiated in Kamp [15] at around the same time (the early eighties) as that of the closely related but independent work of Heim [13]. Central to DRT is the proposal of a level of explicit semantic representation called discourse representation structure. This feature of the analysis, henceforth referred to as representational, was challenged in Barwise [1], where the essential point was argued instead to be to

view the utterance of an expression more dynamically, as having an effect on the environment shared by speaker and hearer, the effect being represented by various sorts of changes in variable assignments. (p. 2)

Shortly afterwards, Groenendijk and Stokhof [11], confining their attention to first-order formulas, defined a simple non-representational translation, dubbed Dynamic Predicate Logic (DPL), of first-order formulas into programs from (Quantified) Dynamic Logic (e.g., Harel [12]). More recently, further developments of DRT have appeared in the textbook Kamp and Reyle [14], far outstripping Kamp [15], Barwise [1] and Groenendijk and Stokhof [11]. These include an account of generalized quantifiers and plurals (going back to 1985/86) reported in chapter 4 of the book. Although certain notions in that chapter admit straightforward transcriptions to a DPL-framework (e.g., the two different semantics of duplex conditions in Kamp and Reyle [14], that are christened weak and strong readings in Chierchia [5]) and although some interesting extensions of DPL are suggested in Van den Berg [2, 4] (as well as Chierchia [5] and Van Eijck and De Vries [7]), it is not clear that a nonrepresentational treatment of generalized quantifiers comparable in scope and perspicuity to that in Kamp and Reyle [14] has been worked out. The present paper is intended as a contribution towards that end.

The linguist is, of course, entitled to ask why bother developing yet another formalism with the same empirical coverage? In fact, it is not obvious to the present author that the scope of the proposal below is confined to chapter 4 of Kamp and Reyle [14]. But at any rate, the hope is that different formal approaches reflect different intuitions that throw light on issues with genuine “linguistic” content. An intuition stressed by the “dynamic” approach (exemplified by DPL) is that the meaning of a statement lies not so much in its truth relative to a context, but in the change in context that it induces. Formalizing statements as formulas, and contexts as states, the idea is captured by the slogan “formulas-as-programs”, with a program π reduced semantically to its binary input/output relation ρ(π) ⊆ S × S on some set S of states. As will become clear below, the same scheme can be applied to Kamp [15], with the essential exception that the relevant states in Kamp [15] are the discourse representation structures mentioned above.

By contrast, to support a translation from first-order formulas to programs in quantified dynamic logic, the states in DPL are defined, relative to a firstorder model M, to be functions, henceforth called (M-)substitutions, from a set of variables to the universe of M. A substitution is nothing more than the “variable assignment” mentioned in the quotation above from Barwise [1], and is also referred to elsewhere as an “environment” or a “valuation.” Although our choice of the term “substitution” is largely arbitrary, it can be motivated in part by (i) its compatibility with S, (ii) the unmistakable distinction made from certain programs (to be described shortly) called “random assignments”, and (iii) the suggestion (e..g, from Barwise [1]) that an object in S have as its domain a finite subset of the full (infinite) set X of variables. (This suggestion departs form the conventions of dynamic logic, which are otherwise observed below.) While the present paper will refrain from making a commitment to (iii), except at one point indicated below, let us note in passing that item (iii) yields a more computationally accessible (i.e., realistic) picture that is also more faithful to DRT (in contrast, that is, to the usual convention that a variable assignment is defined on all of X). Keeping (iii) in mind, let us characterize the interpretation of a random assignment x :=?, where x ∈ X, by the condition that for all f and g ∈ S,

f ρ(x :=?) g iff x ∈ dom(g) and f = g except

possibly on x

(iff dom(g) = dom(f) ∪ {x} and

(∀x′ ∈ dom(f) − {x}) f(x′) = g(x′)) .

All changes to a substitution in DPL can be traced to such a random assignment, which is used to interpret existential quantification ∃x. Conjunction & and negation ∼ are analyzed in terms of sequential composition (written ;) and a test for divergence (written ¬, instead of the somewhat more cumbersome notation ([·]⊥)? of dynamic logic), respectively. The remaining logical connectives (including the universal quantifier) can then be derived as abbreviations in the familiar manner, sound for classical logic.

The details will be presented more carefully below, but for now let us stress the computational and dynamic aspects of DPL: a formula φ is translated into a program φ^{DP L}, resulting in an interpretation [φ] of φ as the input/output relation ρ(φ^{DP L}) ⊆ S ×S. DPL’s interpretation of negation, however, features two disturbing conjuncts,

f[∼φ]g iff f = g and f ∉ dom[φ] ,

belying the propaganda above about change and computation, and raising two somewhat embarrassing questions. (Q1) How well is the view that “meaning lies in change” served by reducing

φ ⊃ ψ to ∼(φ& ∼ψ)

and

∀xφ to ∼∃x ∼φ ,

given that the negation of a program can only output its input

f[∼φ]g implies f = g

(assuming it halts at all)? Do not such programs trivialize the shift from a static (truth-centered) semantics to a dynamic semantics?

(Q2) How seriously can the term “program” be taken, given that (under a recursion-theoretic conception) testing for divergence (i.e., the complement of the halting problem),

f ∉ dom[φ] ,

falls beyond the realm of computation? In what sense are such programs computational?

We will address points (Q1) and (Q2) somewhat indirectly, by first focussing on a crucial feature of some programs in DPL — non-determinism.

A program π is non-deterministic if its input/output relation is not functional — i.e., if on some input, π can return one of at least two distinct outputs. Such a possibility is hard-wired in dynamic logic by the binary program connective +, which is interpreted as union

f ρ(π + π′) g iff f ρ(π) g or f ρ(π′) g .

In Peleg [16], a binary program construct ∩ dual to + is introduced yielding a notion of parallelism. Roughly put, if π and π′ are programs from ordinary dynamic logic, then

f ρ(π) g and f ρ(π′) h imply f ρ(π ∩ π′) {g, h} ,

the intuition being that whereas + is disjunctive, ∩ is conjunctive (which should be kept in mind when specifying transitions from {g, h}). More rigorously, ∩ is accomodated by lifting the function ρ to a function ρ̂ with ρ̂(π) ⊆ S × Pow_{+}(S), where Pow_{+}(S) = Power(S) − {∅}. In fact, we will not have any use for ∩, which (for the record) is governed by

f ρ̂(π ∩ π′) U iff (∃V, W) U = V ∪ W and
f ρ̂(π) V and f ρ̂(π′) W .

Nonetheless, the passage from ρ to ρ̂ (along the embedding s ↦ {s} of S into Pow_{+}(S)) will be crucial to the constructs we will introduce, as will Peleg [16]’s clause for sequential composition

f ρ̂(π; π′) U iff (∃V) f ρ̂(π) V and there is a function

F with domain V s.t. (∀g ∈ V) g ρ̂(π′) F (g) and

U = ⋃{F (g) | g ∈ V } .

To understand this clause, think of a substitution as a process (or some snapshot of a process), and regard a set of substitutions (such as U and V above) as a family of proceses running in parallel. The universal quantification (∀g ∈ V) above formalizes the conjunctive nature of parallelism.

Our move from S to Pow_{+}(S) will be necessitated by the non-determinism not in +, but in random assignments x :=?. To a first approximation, the idea is to introduce a unary program construct ·_{∀} such that on programs π from dynamic logic,

f ρ̂(π_{∀}) U iff U = {g ∈ S | f ρ(π) g} ≠ ∅ ,

and, in particular,

f ρ̂((x :=?)_{∀}) {g ∈ S | x ∈ dom(g) and f = g

except possibly on x} .

(The effect of ·_{∀} can be pictured as turning the disjunctive branching of a non-deterministic program to the conjunctive branching of a deterministic program.) As ρ̂ is somewhat uneven in that the left and right arguments of ρ̂(π) have different types, it is natural to lift ρ̂ further to a map [[·]] that interprets a program π as a binary relation [[π]] ⊆ Pow_{+}(S) × Pow_{+}(S). (The restriction to non-empty subsets of S is made because ∅ arises from the impossibility of making a ρ-transition.) Just how the lifting is carried out will require some elaboration, but very briefly, the point is that π becomes a second-order program that relates sets of substitutions operating in the conjunctive manner alluded to above. The unary program construct ·_{∀} can be derived from a binary program construct ⇒ introduced in Fernando [10] to extend the DPL translation by the clauses

(φ ⊃ ψ)^{DP L} = φ^{DP L} ⇒ ψ^{DP L}
(∀xφ)^{DP L} = (x :=?) ⇒ φ^{DP L} .

This extension to DPL is “conservative” in that

∼∼(φ ⊃ ψ) ≡ ∼(φ& ∼ψ)
∼∼(∀xφ) ≡ ∼∃x ∼φ ,

where φ ≡ ψ means that φ and ψ are interpreted by the same binary relation (i.e., [φ] = [ψ]). Note that the double negation ¬¬π of a program π is interpreted as {(f, f) | f ∈ dom[[π]]}. The troublesome negation ¬π of a program π can be recast as π ⇒ ⊥, where [[⊥]] = ∅. But, in general, the point is that programs of the form π ⇒ π′ externalize the dynamic effects of programs ¬(π; ¬π′) used in DPL to interpret implication. In short, the construct ⇒ forms our reply to (Q1).

As for (Q2), let us first try to put to rest any doubt about its significance. Referring to dynamic approaches to generalized quantifiers, Van den Berg [3] asserts that Van den Berg [4] “shares with Chierchia and Van Eijck” ([5, 7]) the property “that the dynamic behavior of the quantifier is totally ad hoc. The definition gives a condition in terms of the generalized quantifier and on top of that it gives some condition on the output … There is no reason why either of these definitions, or any of the other proposed in the literature, is natural, let alone the correct one” (p. 2). Such reservations suggest that the computational intuitions behind the term “program” might be worth developing. In fact, the idea of using sets of substitutions (or “assignments”) as “witnesses” occurs already in Van den Berg [2, 4], although the computational metaphor is left undeveloped there. We will return to Van den Berg [2, 4] later on, but for now let us briefly outline the present proposal.

Discourse markers arising from quantification are generated below by a deterministic program of the form

(∗) (x :=? ; π)_{∀} ,

where, roughly, the program π yields the discourse representation structure K in Kamp and Reyle [14]’s abstraction condition

X = ∑ x : K .

The construct ·_{∀} has the additional virtue that it can be understood without mentioning substitutions or variables, and that, moreover, (∗) keeps the functional dependencies of x. Moving on, if a set of substitutions can grow by a program (x :=?; π)_{∀}, that set can also be trimmed by a program

Qx.π ,

where Q is some generalized quantifier. The program Qx.π (which will play a role similar to Kamp and Reyle [14]’s duplex condition) is essentially π, except that the conjunctive (universal) force of π on an input set U of substitutions is weakened so that not all substitutions in U need to execute π. Rather, we require that U be “Qx-related” to the set W ⊆ U of substitutions in U that can halt on π. The italics on “the” is meant to mark the “determinate”^{1} character of the resulting discourse marker, although an “indeterminate” alternative will also be presented below. In either case, the condition W ⊆ U builds in the conservativity of generalized quantifiers. Our interpretation of generalized quantifiers will be assembled from the programs (x :=?; π)_{∀} and Qx.π, taking into account fine points concerning distributive-versus-collective and weak-versus-strong readings. Beyond these linguistic concerns, there are (inevitably?) various formal options that seem to carry no linguistic content, but which nevertheless demand our attention.

With these options as well as the question (Q2) of computability in mind, let us consider the passage (analyzed in Fernando [9]) from DPL transitions (defined relative to a fixed first-order model) to DRT transitions between discourse representation structures (DRS’s). Observe that DRT transitions between DRS’s not only (S1) refer to transitions from various first-order models (in the same manner

that first-order formulas apply to various first-order models), but also (S2) “determinize” the non-deterministic transitions in DPL (following the

classic construction of deterministic finite automaton from non-deterministic finite automaton).

This suggests a two-step passage (spelled out in the concluding section below) from DPL transitions to DRT transitions that can drown out certain details of a DPL transition. The internalization in (S2) of the non-determinism of DPL transitions results in a somewhat more complex notion of state (corresponding to a DRS), built from “disjunctive” non-deterministic sets, as well as dual “conjunctive” parallel sets. Item (S1) points to a certain uniformity in DPL, upon which our answer to (Q2) will be founded. Our contention is that the notion of computation underlying DPL (and DRT) should not be construed in the local sense of ordinary (classical) recursion theory (a theory that applies specifically to the standard model of arithmetic; viz., the natural numbers), but in the global sense of Gödel’s completeness theorem (as opposed to his incompleteness theorems). The terms “program” and “computation” are perhaps somewhat misleading when used in DPL; because the set Π of programs in DPL is closed under negation, there can be no program in Π universal for Π (contrary to the tradition of recursion theory). If, however, the term “program” is replaced by “formula” (and “computation” by “logic”), then this failure of universality is hardly surprising, in view of Tarski’s theorem on the undefinability of truth. (Taking the natural numbers as a concrete example, negation leads to non-arithmeticity.) On the other hand, if one insists in using the words “program” and “computation”, then — and this is our answer to (Q2) — DRT provides for DPL an appropriate representational level of abstraction for such discourse. Computation lives on syntax, and syntax is what DRT supplies in the form of a DRS. The additional computational power that a generalized quantifier Q might be expected to contribute should be understood at the global level, where uniformities in the map from a set M to the binary relation Q_{M} on Power(M) matter.

1The term “determinate” is intended to refer here to something akin to both definite descriptions and deterministic programs. Its antonym “indeterminate” is meant to refer, in the same way, to “unselective” binding, as used in Van der Does [6] (assuming the present author understands Van der Does’ intentions correctly).

The remainder of the present paper is organized as follows. After some technical background on dynamic semantics in section 1, a bit of linguistic data is presented in section 2. Section 3 then considers the passage from S to Pow_{+}(S), concentrating on propositional rather than quantificational matters. A closer look inside substitutions is needed in section 4 for the analysis (proper) of generalized quantifiers. Section 5 turns to some related work (viz., Van den Berg [2, 4] and Van der Does [6]), before section 6 concludes with a review of the essential points of the present work.

1. Between formulas and programs

Let Φ be a set of formulas φ, and Π be a set of programs π. Assume that the formulas and programs are interpreted relative to a fixed set S of states by functions | · | and ρ respectively such that for every φ ∈ Φ, |φ| ⊆ S, while for every π ∈ Π, ρ(π) ⊆ S × S, the intuition being that

|φ| ≈ {s ∈ S | φ is true at s}

and

ρ(π) ≈ {(s, t) ∈ S × S | given input state s,

π can halt on output state t} .

Beyond the broad question of how formulas relate to programs, the present paper is concerned with what the word “can” (in the line above for ρ(π)) means in the presence of non-determinism.

Consider the embedding ·? : Φ → Π of formulas φ into programs (tests) φ?, given by ρ(φ?) = Δ|φ|, where ΔU is the diagonal {(s, s) | s ∈ U}. Going the opposite direction, define the projection ⟨·⟩⊤ : Π → Φ of programs π into formulas ⟨π⟩⊤, by |⟨π⟩⊤| = domρ(π). A system of dynamic semantics such as DPL amounts to a translation of formulas φ into programs π_{φ}, that in turn assert ⟨π_{φ}⟩⊤. Now, certainly, for the case where S is the set of substitutions (mentioned in the introduction), the usual Tarskian definition can be obtained by setting

|φ&ψ| = |⟨φ?; ψ?⟩⊤|
| ∼φ| = |⟨¬(φ?)⟩⊤|
|∃xφ| = |⟨x :=?; φ?⟩⊤| ,

where

ρ(π; π′) = ρ(π) ∘ ρ(π′)
(= {(f, g) ∈ S × S | (∃h) f ρ(π) h and
h ρ(π′) g})
ρ(¬π) = {(f, f) | f ∈ S − domρ(π)}

and ρ(x :=?) is as described in the introduction. It turns out, however, that the translation φ ↦ φ^{DP L} given by

R(\overline{t})^{DP L} = R(\overline{t})?
(φ&ψ)^{DP L} = φ^{DP L} ; ψ^{DP L}
(∼φ)^{DP L} = ¬(φ^{DP L})
(∃xφ)^{DP L} = x :=? ; φ^{DP L}

has a different effect than the translation φ ↦ φ? in that the proposition ⟨φ^{DP L}⟩⊤ (asserted by φ^{DP L}) is not equivalent (under ρ) to the proposition ⟨φ?⟩⊤ (asserted by φ?). The reason, quite simply, is that although a formula φ is equivalent to ⟨φ?⟩⊤, a program π may differ from ⟨π⟩⊤?, the latter of which is equivalent to the static projection ¬¬π (interpreted as Δdomρ(π)). The dynamic effect of x :=? is useful for introducing a (singular) pronoun by an existential quantifier, as exemplified by the notorious donkey sentence

if a farmer owns a donkey then he beats it ,

which can be formalized naively as

(∗) (∃x, y) (f(x) & o(x, y) & d(y)) ⊃ b(x, y) .

DPL translates (∗), in turn, to the program

¬ (x :=?; y :=?; f(x)?; o(x, y)?; d(y)? ; ¬b(x, y)?) ,

following the equalities

(φ ⊃ ψ)^{DP L} = (∼(φ& ∼ψ))^{DP L}
= ¬(φ^{DP L} ; ¬ψ^{DP L}) .

The program scheme ¬(π; ¬π′) generated by the DPL translation of implication occurs again in the DPL translation of universal quantification

(∀xφ)^{DP L} = (∼∃x ∼φ)^{DP L}
= ¬(x :=? ; ¬φ^{DP L}) .

Papers on Dynamic Semantics and Related Topics 15

The outer negation blocks the introduction of discourse markers (for plurals).^{2} To overcome the static effect of negation ¬, a binary program construct ⇒ is introduced in Fernando [10] that externalizes the dynamism within ¬(π; ¬π′) by collecting (in the output) witnesses g′ to the ∀∃-clause in

f ρ(¬(π; ¬π′)) g iff f = g and (∀f′ s.t. f ρ(π) f′)
(∃g′) f′ ρ(π′) g′ ,

the idea being that the “process f spawns” the processes g′. The first proposal in Fernando [10] is (P1) to introduce functional states:

s [[π ⇒ π′]]_{1} F “iff” (s ∉ dom[[π]]_{1} and s = F) or

(s ∈ dom[[π]]_{1} and F is a function with domain {s′ | s[[π]]_{1}s′} s.t. (∀s′ s.t. s[[π]]_{1}s′)

s′[[π′]]_{1}F (s′)) .

Implicit above is a passage from S to the least solution S_{1} to S_{1} = S ∪ (S_{1} ⇁ S_{1}), where A ⇁ B is the set of partial functions from A to B. A relation R ⊆ S × S can be lifted canonically to R̂ by requiring that for functions F ∈ S_{1} − S (and for all G ∈ S_{1}),

F R̂ G iff dom(F) = dom(G) and
(∀s ∈ dom(F)) F (s) R̂ G(s) .

A simplification of (P1) is (P1.5) to replace the function F by its image U

s [[π ⇒ π′]]_{1.5} U “iff” (s ∉ dom[[π]]_{1.5} and s = U)

or (s ∈ dom[[π]]_{1.5} and there is a function F : {s′|s[[π]]_{1.5}s′} →_{onto} U s.t. (∀s′ s.t. s[[π]]_{1.5}s′) s′[[π′]]_{1.5}F (s′)) .

That is, pass from S to the least solution S_{1.5} to S_{1.5} = S ∪ Pow_{+}(S_{1.5}). A further simiplification of (P1) is

(⟨π⟩φ)? ≡ ¬¬(π ; φ?)
([π]φ)? ≡ ¬¬(π ⇒ φ?) ,

2The reader familiar with dynamic logic can cast (∀xφ)^{DP L} as [x :=?]⟨φ^{DP L}⟩⊤?, and view the present problem as identifying a program counterpart ⇒ to the box/square modalities, playing a role analogous to that of ; for the diamond/angle modalities where ≡ is semantic equivalence.

(P2) to project S_{1.5} into Pow_{+}(S) by embedding S into Pow_{+}(S) via f ↦ {f} and collapsing Pow_{+}(Pow_{+}(S)), Pow_{+}(Pow_{+} (Pow_{+}(S))), etc. to Pow_{+}(S) by suitable iterations of union. That is, project S_{1.5} into Pow_{+}(S) by the map ˜· defined by

s̃ = \{ \begin{matrix}\{s\} & if s ∈ S \\ s & if s ∈ Pow_{+}(S) \\ ⋃\{t̃ | t ∈ s\} & otherwise. \end{matrix}

There are at least two complications facing the proposals above.

(i) First, the map R ↦ R̂ in (P1) does not commute with, for example, the interpretation ∪ of +,

ˆ (R ∪ R′) need not equal R̂ ∪ R̂′ .

Neither does it commute with ¬. Nor do matters improve when passing to (P1.5) or to (P2).

(ii) In (P1.5) or (P2), it is not clear how, proceeding from (P1), to collapse S_{1} to S_{1.5} or S_{2}, without the information (in the mapping F) about how processes are spawned. In place of the canonical map R ↦ R̂ of (P1), there are (as explained in section 3) at least two non-equivalent ways of lifting a binary relation on S to a binary relation on Pow_{+}(S), consistent with a conjunctive reading of the non-empty sets of substitutions.

As will be shown below, item (i) carries genuine linguistic content (pointing, as it does, to the difference between so-called collective and distributive readings). Whether or not item (ii) does is unclear to the present author.

2. Some linguistic data

Sentences such as the following suggest that singular pronouns tend to have indeterminate references, while plural pronous introduced by generalized quantifiers tend to be determinate.

(1) A/some congressman admires Kennedy. He is very junior.
(2) Some congressmen admire Kennedy. They are very junior.

“He” in (1) is some (indeterminate) congressman who admires Kennedy. “They” in (2) is, according to Evans [8], an E-type pronoun referring to all congressmen who admire Kennedy. Its determinateness suggests that a plural object must be definable (possibly in first-order logic). The truth conditions for (2) contrast with those for

(3) Some congressmen admire Kennedy and are very junior.

(3) has the same truth conditions as

(4) Some congressmen admire Kennedy. Some of

them are very junior.

However, “they” would seem to have different available meanings in (3) and (4): follow up (4) with

(4b) Most are quite senior.

A somewhat minor point is whether a discourse marker should be kept.

(5) Some congressmen admire Kennedy. Two of them

are very junior. Three are somewhat senior. Both are in their early thirties.

(4b) and (5) suggest that discourse markers should not be destroyed (but perhaps copied to some new variable).

In fact, the determinatenes of generalized quantifiers is somewhat controversial. It is felt by some that the line

two congressmen admire Kennedy

does not imply that at most two congressmen admire Kennedy. (Consider the analysis in Kamp and Reyle [14], p. 378 of “two of them” by some indeterminate V.) But then an E-type reading of

Two congressmen admire Kennedy. They are very junior.

makes “they” refer to all congressmen who admire Kennedy. Even if we concede that “two” is ambiguous between “exactly two” and “at least two”, the creation of a discourse marker “they” suggests that there are exactly two such congressmen. Or is an indeterminate choice of such a pair from a model where there are more than two allowed? Both options will be explored below.

Then there is also the question of what it means for the group to admire Kennedy. Even if, simplifying matters, we agree that each one in the group must admire Kennedy, there is more trouble ahead. The sentence

(6) they are very junior or very silly

has the collective reading

all of them are very junior, or all of them are very silly

(where “or” has scope outside “they”), and the distributive reading

each one of them is either very junior or very silly

(where “or” has scope inside “they”). Similarly, turning to negation,

(7) they are not very junior

has the distributive reading

each one of them is not very junior ,

and the collective reading at least one of them is not very junior .

There will be no avoiding such complications in our formalization.

Finally, let us turn to a point often made about the proposal in Fernando [10], on which the present paper builds. Although it is true enough that the line

Each student told a joke. She forgot the punchline.

(from Barwise [1]) sounds anomalous, suggesting that the discourse marker for a noun phrase that is universally quantified should not be available beyond the sentence in which it occurs, it is equally true that lines such as

Every player chooses a pawn. He puts it on square one.

(from Groenendijk and Stokhof [11]) suggest otherwise. The former suggestion is available in Fernando [10] via the usual classical reduction (adopted in DPL) of ∀ and ⊃ in terms of negation, ∃ and conjunction. The latter suggestion is also within the scope of Fernando [10]. But alas, just how to choose between these two options is not. The present paper will be full of this sort of embarrassment of riches.

3. Second-order programs

The present section is concerned with a passage from relations on S to relations on Pow_{+}(S), pictured by

\frac{ρ(π) ⊆ S × S}{[[π]] ⊆ Pow_{+}(S) × Pow_{+}(S)}

along the embedding f ↦ {f} of S into Pow_{+}(S), so that for the programs π from ordinary dynamic logic,

{f}[[π]]{g} iff f ρ(π) g .

(Recall that the empty set ∅ is excluded as it arises from the failure of a substitution to make a ρ-transition.) There is some freedom in choosing exactly how to pass from ρ to [[·]], even if we require that a set U ∈ Pow_{+}(S) of substitutions should be treated in a conjunctive (parallel) manner, dual to the disjunctive manner of non-determinism. A binary relation R on S can be lifted to a binary relation on Pow_{+}(S) as

↑R = {(U, V) ∈ Pow_{+}(S) × Pow_{+}(S) | ∃ function F from
U onto V s.t. (∀s ∈ U) s R F (s)}

(which is implicit in the interpretation of ; in Peleg [16]) or else (non-equivalently) as

⇑R = {(U, V) ∈ Pow_{+}(S) × Pow_{+}(S) |
(∀s ∈ U)(∃t ∈ V) sRt and (∀t ∈ V)(∃s ∈ U) sRt} .

Comparing these with the the inductive clauses from dynamic logic, note that (↑ R) ∘ (↑ R′) need not equal ↑ (R ∘ R′), as pointed out to the author by A. Visser. On the other hand, (⇑ R) ∘ (⇑ R′) is ⇑ (R ∘ R′), at the cost of some looseness in the embedding f ↦ {f} (already for random assignments).

Unfortunately, neither ↑ nor ⇑ commutes with ∪, although it is easy enough to motivate the failure here by the ambiguity in sentence (6) from the previous section. Similar complications surround negation, as illustrated by (7).

For the sake of concreteness, let us agree that if π is a random assignment x :=? or a test φ?, then [[π]] =↑ρ(π). Then, proceeding inductively, define (for collective readings)

[[π; π′]] = [[π]] ∘ [[π′]]
[[π + π′]] = [[π]] ∪ [[π′]]
[[¬π]] = {(s, s) | s ∈ Pow_{+}(S) − dom[[π]]} ,

further closing the programs (if the reader desires) under unary program constructs ·_{↑} and ·_{⇑}, subject to

[[π_{↑}]] = {(U, V) | U ∈ Pow_{+}(S) and there is a
function F with domain U s.t. V = ⋃_{s∈U} F (s)
and (∀s ∈ U) {s}[[π]]F (s)}
[[π_{⇑}]] = {(U, V) ∈ Pow_{+}(S) × Pow_{+}(S) | (∀s ∈ U)
(∃W ⊆ V) {s}[[π]]W and
(∀t ∈ V)(∃W ⊆ V)(∃s ∈ U)
{s}[[π]]W and t ∈ W } .

This allows a formulation of distributive alternatives (π; π′)_{↑}, (π + π′)_{↑}, (π + π′)_{⇑}, and (¬π)_{↑} (= (¬π)_{⇑}) to π; π′, π + π′, etc. Turning finally to the reason for passing from S to Pow_{+}(S), define

U[[π ⇒ π′]]V iff (U ∉ dom[[π]] and U = V) or

(U ∈ dom[[π]] and there is a function F with domain {U′ | U[[π]]U′} s.t.

V = ⋃{F (U′) | U′ ∈ dom(F)} and

(∀U′ ∈ dom(F)) U′[[π′]]F (U′)) .

Observe that

[[¬¬(π ⇒ π′)]] = [[¬(π; ¬π′)]]
[[¬π]] = [[π ⇒ ⊥]]

(where [[⊥]] = ∅), although the equivalence between ¬π and ([π]⊥)? is lost. A program counterpart π_{∀} to the box modality [π] on formulas of dynamic logic that turns the usual “or” branching of Kripke frames into “and” branching,

U[[π_{∀}]]V iff V = ⋃{U′ | U[[π]]U′} (≠ ∅) ,

can then be derived as

π_{∀} = ¬¬π ; (π ⇒ ⊤) ,

where ⊤ = ¬⊥. Going the opposite direction,

[[π ⇒ π′]] = [[(π_{∀}; π′) + ¬π]]

provided π′ is distributive in the sense of ↑ (i.e., [[π′]] = [[π′_{↑}]]) or π is deterministic. Although random assignments and tests are defined to be distributive, it is easy to manufacture a non-deterministic choice π_{1} + π_{2} (e.g., from tests) that is not.

Of the two ways of turning an arbitrary program into a deterministic program, ¬¬· is static, whereas ·_{∀} is dynamic. Notice that if π is deterministic, then [[π]] = [[π_{∀}]]. In particular, as ¬π is always deterministic, whether or not π is, [[¬π]] = [[(¬π)_{∀}]]. It is also easy to see that [[¬π]] = [[¬(π_{∀})]]. Recalling the construct ∩ of Peleg [16], note that if π and π′ are deterministic, then π ∩ π′ can be coded as (π + π′)_{∀}.

4. Generalized quantifiers

Given a generalized quantifier Q that maps the universe M of a first-order model to a binary relation Q_{M} on Power(M), Chierchia [5] (as well as Van Eijck and De Vries [7]) extend quantified dynamic logic by binary programs Qx(π, π′) (for x ∈ X and programs π and π′), interpreting it (by an extension of ρ) as the externally static test

{(s, s) | s ∈ S and {m ∈ M | ∃s′ s[x/m] ρ(π) s′} Q_{M}
{m ∈ M | ∃s′ s[x/m] ρ(π; π′) s′}} .

This corresponds to what Chierchia [5] calls the “weak” reading, which is presented as line (4.166) in p. 421 of Kamp and Reyle [14], for the semantics of duplex conditions. The alternative “strong” reading

{(s, s) | s ∈ S and {m ∈ M | ∃s′ s[x/m] ρ(π) s′} Q_{M}
{m ∈ M | ∃s′ s[x/m] ρ(¬(π; ¬π′)) s′}} .

(corresponding to line (4.172), p. 424 of Kamp and Reyle [14]) is also offered in Chierchia [5] (and Van Eijck and De Vries [7]). In either case, a basic point of the present work is to externalize the dynamic effects so as to support the imposition of further constraints on variables introduced by generalized quantifiers. That is, our analysis of a generalized quantifier Q will incorporate the abstraction condition of Kamp and Reyle within our mechanism for their duplex condition. We will modify the notation Qx(π, π′) slightly by writing (Qx : π)π′ for our proposal.

Concentrating first on the strong reading, consider the interpretation

(All x : π)π′ = (x :=?; π) ⇒ π′

implicit in Fernando [10]. This is semantically equivalent, if [[π′]] = [[π′_{↑}]], to

(x :=?; π)_{∀} ; π′ + ¬(x :=?; π) .

For the remainder of this section, let us not be distracted by the question of the distributivity of π′, as this can always be arranged by replacing π′ by π′_{↑}. (Similarly, throughout this section, the non-determinism suggested by + will be spurious, as the disjuncts will be mutually exclusive.) Using certain programs that will be explained shortly, let us generalize the interpretation above of All to Q by equating (Qx : π)π′ with

(x :=?; π)_{∀} ; (Qx.π′ + ⟨Q^{−}x⟩; ¬π′) +
¬(x :=?; π) ; ⟨Q^{0}x⟩

where All x.π is (under [[·]]) just π, ⟨All^{−}x⟩ is ⊥ (i.e., [[⟨All^{−}x⟩]] is ∅), and ⟨All^{0}x⟩ is ⊤ (i.e., [[⟨All^{0}x⟩]] is equality on Pow_{+}(S)). More generally, the new programs Qx.π (for every program π), ⟨Q^{−}x⟩, and ⟨Q^{0}x⟩ are interpreted on the basis of the relation

Q_{M}x = {(U, V) ∈ Pow_{+}(S) × Pow_{+}(S) |
{s(x) | s ∈ U} Q_{M} {s(x) | s ∈ V }}

as follows

[[Qx.π]] = {(U, V) ∈ Pow_{+}(S) × Pow_{+}(S) |
U Q_{M}x ⋃{W ⊆ U | W ∈ dom[[π]]} and
⋃{W ⊆ U | W ∈ dom[[π]]} [[π]] V }
[[⟨Q^{−}x⟩]] = {(U, U) | U ∈ Pow_{+}(M) and U Q_{M}x ∅}
[[⟨Q^{0}x⟩]] = {(U, U) | U ∈ Pow_{+}(M) and ∅ Q_{M}x ∅} .

Conservativity is essentially built in, not only in the semantic clause for Qx.π (via the condition W ⊆ U), but also in the test ⟨Q^{0}x⟩, which is an all-or nothing affair (being either ⊤ or ⊥). The intuition behind Qx.π is that π is executed without necessarily insisting that every substitution in the input state U can halt on π, but rather that U is Q_{M}x-related to the set of substitutions in U that can halt on π. The program Qx.π can be decomposed as the sequential composition

Qx.¬¬π ; π

of a deterministic program Qx.¬¬π with π, since [[Qx.¬¬π]] incorporates the first of [[Qx.π]]’s two conjuncts, plus a tiny bit more

[[Qx.¬¬π]] = {(U, V) ∈ Pow_{+}(S) × Pow_{+}(S) |
V = ⋃{W ⊆ U | W ∈ dom[[π]]} and
U Q_{M}x V and V ∈ dom[[π]]} .

Although the unary program constructs Qx.· and Qx.¬¬· are, in the presence of sequential composition and negation, interdefinable (so that either could be taken as primitive), it is quite another matter (as we will see shortly) to reduce these unary constructs to a nullary construct ⟨Q^{+}x⟩, independent of π.

The external dynamic effects of a program fragment π can always be suppressed by prefixing the appropriate program fragment by double negation ¬¬.

Such effects are, of course, crucial in interpreting inter-sentential anaphora, which allows constraints on pronouns to be imposed by incremental updates. Double negation ¬¬ is useful for encoding the weak reading of (Qx : π)π′ as

(x :=?; ¬¬π)_{∀} ; (Qx.(π; π′) + ⟨Q^{−}x⟩; ¬(π; π′)) +
¬(x :=?; π) ; ⟨Q^{0}x⟩ .

Because the dynamic effects of π are suppressed in (x :=?; ¬¬π)_{∀}, the program π must (in contrast to the strong reading) be repeated in (Qx.(π; π′) + ⟨Q^{−}x⟩; ¬(π; π′)).

Next, let us turn to a deviant treatment of quantification, resulting from replacing Qx.π by the sequential composition

⟨Q^{+}x⟩ ; π

of a program ⟨Q^{+}x⟩ with π, where the program ⟨Q^{+}x⟩ chooses some nonempty subset V of the input set U to which U is Q_{M}x-related

[[⟨Q^{+}x⟩]] = {(U, V) ∈ Pow_{+}(S) × Pow_{+}(S) |
UQ_{M}xV and V ⊆ U}.

The sequential composition with π then means that V must execute π.^{3} Setting aside dynamic complications, to say that for all sets A and B,

(∗) AQ_{M}B iff (∃C) AQ_{M}C and C ⊆ B

is to suppose that Q is upwards-monotone on its second argument (e.g. ∀, ∃). Even in that case, however, the discourse marker (“they”) introduced by the quantification must refer (according to the E-type account) to A ∩ B, and not to A ∩ C, for some indeterminate choice of C. If Q is not upwardsmonotone on its second argument, then (∗) fails even under a modification of (∗) where C is required to be maximal (as can be seen by taking, for example, Q to be “exactly two”). If the non-deterministic program ⟨Q^{+}x⟩ is ruled out, then it is plausible that the only sets of substitutions required (as inputs to and outputs of programs) are first-order definable, with parameters (for the “singular” variables).

5. Related work

As has already been pointed out in the introduction, the present work borrows from Peleg [16] the idea of a “conjunctive” set, but differs from it by introducing such sets not by ∩ but by ⇒ (to capture a notion of parallelism dual to the non-determinism in x :=?, rather than in +). Conjunctive sets also appear in Van den Berg [2, 4], but again not via ⇒ (or ·_{∀}). Instead, a 3-valued logic is employed in Van den Berg [2, 4] to make a “plural logic” dynamic (although the present author cannot claim to understand exactly how this feat is carried out).

3A comparison with the indeterminate treatment of “two of them” in Kamp and Reyle [14], p. 378 is instructive here.

Next, let us say a few words about the system Dynamic Quantifier Logic (DQL) of Van der Does [6]. A basic premise of DQL is that singular pronouns involve “unselective binding”^{4}, while plurals are given by (E-type) descriptions (rather than some possibly indeterminate notion of maximality). Given a model with universe D, DQL interprets formulas relative to triples (a, c, h) of

(i) assignments a; i.e., functions from the set of variables to D (called substitutions above);

(ii) contexts c; i.e., partial functions from the set of variables to formulas; and (iii) choice functions h; i.e., functions from subsets of D to D (used for

unselective binding on singulars). (Assignments a are merged with choice functions h in Van der Does’ later work, although this is a rather minor point.) The main idea, as Van der Does writes in his abstract for the Ninth Amsterdam Colloquium, is as follows.

In my system, as in others, pronouns are quantifiers which depend for their interpretation on parametrized context sets. Plural pronouns are interpreted as a universal quantifier over such a context set, while singular pronouns involve a choice from such a set …

Is he thus committed to a distributive reading of plurals? Whether or not he is, the general picture seems to be in accord with our determinate analysis above. A somewhat alarming difference, however, is that DQL “is best thought as a standard ‘static’ logic, which comes with a separate dynamic module to handle the context generated by a text” (Van der Does [6], p. 20); “DQL uncouples the interpretation of a formula from its context change potential” (p.25). The context change potentials associated with formulas are functions from contexts to contexts. If, however, transitions are given by functional context change potentials, what becomes of the non-determinism in DPL transitions? As the non-determinism in DPL arises (only) from the random assignments used for singular pronouns, presumably DQL has no trouble dealing with that via its choice functions. But alas, the present author must confess that it is not clear to him (at the time of writing) exactly how DQL relates to DPL, let alone to the extension of DPL proposed above.

6. Discussion

The extension to DPL proposed above is based on

(i) generating “conjunctive” sets U of substitutions through a program

construct ·_{∀}, and

(ii) weakening the “universal” force of a program π on such a set U according to a generalized quantifier Q by forming the program Qx.π.

4Roughly, indeterminateness; see footnote 1.

The reader familiar with chapter 4 of Kamp and Reyle [14] might regard ·_{∀} as a mechanism for abstraction, and Qx.· as a tool for the duplex condition.^{5} But, in fact, the constructs ·_{∀} and Qx.· can be explained without mentioning DRT — and, in the case of ·_{∀}, without mentioning variables —, proceeding instead from computational intuitions involving a form of duality between nondeterminism and parallelism. The linguistic relevance of the present work rests on the degree to which the distinction between definite and indefinite noun phrases can be captured by that between deterministic and non-deterministic programs. By providing for conjunctive branching, ·_{∀} yields, from a dynamic viewpoint, more interesting deterministic programs than the static projection ¬¬·. Furthermore, it is a trivial matter to derive ·_{∀} from a binary program construct ⇒ introduced in Fernando [10] to extend the DPL translation.

As earnestly as the present author has tried to motivate his proposals, the reader sensitive to “ad hoc-kery” might worry all the same about some five branch-points that were faced along the way: (B1) the choice in section 1 (of an extension to higher types) between pro-

posals (P1), (P1.5) and (P2) (B2) within (P1.5) and (P2), the choice (of a lifting from relations on S to

relations on Pow_{+}(S)) between ↑· and ⇑· (in section 3) (B3) distributive versus collective readings (B4) weak versus strong readings and (B5) the determinateness or indeterminateness of discourse markers intro-

duced by generalized quantifiers. Of (B1) to (B5), the last three obviously have, for a linguist, some substance. As for the first two points, however, the question is who cares? Whether these options matter can be investigated (by formulating items (S1) and (S2) in the introduction) using the somewhat simple-minded notion of a (pointed)

π_{K} sends the empty DRS to the DRS K.

5More precisely, the present author claims that if K is the set of DRS’s given up to chapter 4 of Kamp and Reyle [14], and if Π is the set of programs from above, then a mapping K ↦ π_{K} can be defined from K to Π, with the property that Briefly, the main point of the inductive definition of the mapping would be to encode

(i) abstraction X = ∑ x : K by (x :=?; π_{K})_{∀} + ¬(x :=? ; π_{K}), and

(ii) the duplex condition with restrictor K, quantifier Q, principal discourse referent x

and scope K′ by ¬¬(Qx : π_{K})π_{K′}, for some binary program construct (Qx : ·)· defined as in section 4 using ·_{∀} and Qx.·.

As indicated in the introduction, (x :=?; π_{K})_{∀} preserves the functional dependencies of x in K. Furthermore, inasmuch as (Qx : ·)· already incorporates the effect of abstraction, it can be argued that (Qx : ·)· is not subject to the criticism made in Van den Berg [3] “that the dynamic behavior of the quantifier is totally ad hoc. The definition gives a condition in terms of the generalized quantifier and on top of that it gives some condition on the output … ” (On the other hand, this very decomposition points to the conjecture that all sets of substitutions needed are first-order definable.)

transition system, a 4-tuple ⟨S, L, →, s_{0}⟩, where S and L are non-empty sets, whose elements are called states and labels respectively, → ⊆ S × L × S is a transition predicate, and s_{0} ∈ S is an initial state. The semantics of DPL can be characterized, relative to a first-order model M and an infinite set X of variables, by a transition system [[M]] = ⟨X →_{fin} M, Φ, [[·]]_{M}, ∅⟩, where

(i) the state set X →_{fin} M is the set of M-substitutions; i.e., functions from finite subsets of X to the universe M of M,

(ii) the label set Φ is the set of first-order formulas (with the signature of

M) over the set X of variables, (iii) the transition predicate [[·]]_{M} associates with every φ ∈ Φ the binary

relation [[φ]]_{M} on X →_{fin} M, given by ρ(φ^{DP L}) (modified in the obvious way for finite functions), and

(iv) the initial state ∅ is the totally undefined function. Similarly, the various options in (B1) and (B2) yield transition systems, albeit somewhat more complicated ones. A transition system for Kamp [15] can also be constructed, independent of some first-order model M, by taking DRS’s as its states, among which the empty DRS is initial; call that transition system DRT. Notice that whereas transitions in DRT are deterministic, those in [[M]] are not. But it is easy enough to make the transitions in [[M]] deterministic by passing to the transition system D([[M]]), given by the map D on transition systems that sweeps the non-determinism underneath states (formed as “disjunctive” sets, dual to the conjunctive sets above). (As mentioned in item (S2) of the introduction, D is essentially the classic construction of deterministic finite automata from non-deterministic ones.) It turns out (as shown in Fernando [9]) that the transition system DRT is isomorphic to the obvious transition system sum

∑ {D([[M]]) | M ∈ M}

over the class M of (say countable) first-order models M (of the appropriate signature). (The formation of the sum above captures the uniformity mentioned in item (S1) of the introduction.) That is, as states go, DRS’s embody a good deal of partiality and complexity, hiding ghastly details from the transition predicate. The transformations D and ∑ together bridge the gap between DPL and DRT (mentioned as items (S1) and (S2) in the introduction) that can be depicted as follows.

DPL  DRT

states substitution

DRS

transitions non-deterministic

deterministic

semantic  syntactic
local  global
labels formula program

Now returning to the ad hoc-kery in (B1) and (B2) above, the point is to compare the transition systems they induce modulo D and ∑. Much work remains to be done.

Acknowledgments

My thanks to colleagues in Amsterdam (Martin van den Berg, Jan van Eijck), Utrecht (Kees Vermeulen, Albert Visser), Stuttgart (Ede Zimmermann) and Edinburgh (David Milward, Massimo Poesio) for comments on oral and/or written presentations of this work.

References

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

[2] Martin van den Berg. Dynamic generalized quantifiers. In J.M. van der Does and J. van Eijck, editors, Generalized Quantifier Theory and Applications. Dutch Network for Language, Logic and Information Prepublication, Amsterdam, 1991. Revised version to appear as CSLI Lecture Notes.

[3] Martin van den Berg. A direct definition of generalized dynamic quantifiers. Preliminary abstract submitted to the Ninth Amsterdam Colloquium, 1993.

[4] Martin van den Berg. Full dynamic plural logic. In K. Bimbó and A. Máté, editors, Proc. 4th Symposium on Logic and Language. Budapest, 1993.

[5] Gennaro Chierchia. Anaphora and dynamic logic. ITLI Prepublication, University of Amsterdam, 1990.

[6] Jaap M. van der Does. The dynamics of sophisticated laziness. Manuscript, ILLC, Amsterdam, September 1993.

[7] J. van Eijck and F.J. de Vries. Dynamic interpretation and Hoare deduction. J. Logic, Language and Information, 1, 1992.

[8] Gareth Evans. Pronouns. Linguistic Inquiry, 11(2), 1980.

[9] Tim Fernando. Transition systems and dynamic semantics. In D. Pearce and G. Wagner, editors, Logics in AI, LNCS 633 (subseries LNAI). Springer-Verlag, Berlin, 1992. A slightly corrected version has appeared as CWI Report CS-R9217, June 1992.

[10] Tim Fernando. The donkey strikes back. In Proc. of the 6th Conference of the European Chapter of the Association for Computational Linguistics. OTS, Utrecht, The Netherlands, 1993.

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

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

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

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

[15] Hans Kamp. A theory of truth and semantic representation. In J. Groenendijk, T. Janssen, and M. Stokhof, editors, Formal Methods in the Study of Language. Mathematical Centre Tracts 135, Amsterdam, 1981.

[16] David Peleg. Concurrent dynamic logic. J. Assoc. Computing Machinery, 34(2), 1987.