Preface

Collected here are most of the papers that I have completed since arriving at the Institut für maschinelle Sprachverarbeitung in December 1993. As much as I wanted to, I have decided not to make any revisions, as that would have further delayed the appearance of the present report. Missing from this collection are (in addition to a number of attempts that got nowhere)

[Bpl] Bisimulations and predicate logic

[Wdr] What is a DRS?

[Lca] A logical connective for ambiguity requiring disambiguation

[Ccp] Are context change potentials functions? and

[Xm] Expecting many (with Hans Kamp).

[Bpl] appears in the Journal of Symbolic Logic (Volume 59, Number 3, September 1994), while [Wdr] and [Lca] are in DYANA deliverables (R2.1.B, December 1994 and R2.2.B, September 1995, respectively). [Ccp] and [Xm] are planned for SFB reports with other authors. ([Xm] can also be found in the proceedings of SALT VI.)

As for the papers included here, each is intended to be more or less selfcontained. Accordingly, they can be read in any order, although a few words might be helpful for orientation.

The DRT analysis of plurals and generalized quantifiers poses, as noted in a recent paper by Hans Kamp,^{1} a problem for non-representational approaches (such as DPL). [1]^{2} proposes an arguably drastic solution, extending, as it does, the notion of state in dynamic logic (in DRT terms, a model-embedding pair) to support parallel computation. Although the presentation in [1] is, I fear, somewhat dense (if not cluttered), it is easy enough now (three years later) to isolate its key idea: the program construct ·_{∀} that generates conjunctive branching, dual to the disjunctive branching underlying the dynamic treatment of indefinites. (Conjunctive and disjunctive branching co-exist in “and-or” graphs, familiar in analyses of games and in Concurrent Dynamic Logic.) [1] can, I think, be pushed much further: on the purely formal side, it provides some common ground for relating the different notions of state in dynamic semantic, game-theoretic and type-theoretic approaches; on the linguistic side, it raises the question of just what is at stake in choosing between the various options available. (I hope to say something about these matters in the near future.)

1“DRT and dynamic semantics: representational and non-representational accounts of anaphora.”

2Papers in this report are numbered (for present reference) in the order in which they appear.

[1] Generalized quantifiers as second-order programs — “dynamically” speaking, natu-

rally. In Proceedings, Ninth Amsterdam Colloquium (December 1993), Universiteit van Amsterdam.

[2] On the computational significance of consistency: from ordinary to generalized re-

cursion theory. Presented at a conference on Proof Theory, Provability Logic and Computation (Berne) March 1994.

[3] Are boxes just parentheses? Manuscript, December 1994.

[4] Computational foundations for dynamic accounts of presuppositions. Presented at

a workshop on Computational Logic for Natural Language Processing (Edinburgh), April 1995.

[5] A persistent notion of truth in dynamic semantics. In Logic, Language and Com-

putation, J. Seligman and D. Westerståhl, eds. CSLI Lecture Notes Number 58, Stanford, 1996.

Instead of pursuing the complications presented by plurals, I turned my attention next to presupposition, out of the concern that the treatment of singular noun phrases that lay in the background of [1] was fatally flawed. Oversimplifying things a bit, [4] was my somewhat panicked reaction to not knowing “what comes first in dynamic semantics.” Particularly alarming to me were claims that the model-embedding-pair notion of state (which I had taken for granted from DRT) is hopelessly inadequate for presupposition (not to mention Veltman’s construct might). The conclusion I reached in [4] is that while model-embedding pairs do not tell the full story, they can nevertheless serve as useful starting points — at least, that is, for semantics conceived as an enterprise centered on questions of truth. But then how is “truth” to be understood within dynamic semantics? A reassuringly “classical” and disappointingly “static” answer is supplied in [5], a paper I have often regretted not giving the title “A Boolean-valued notion of truth for (a) change.” The connection of [5] with presupposition rests on characterizations of presupposition error as the failure of bivalence. A bivalent interpretation amounts, in Boolean-valued semantics, to a “Boolean-valued” model, in which the Boolean algebra is the 2-element algebra 2. As it is well known how

(∗) to turn an arbitrary Boolean-valued model into an ordinary 2-valued model (through division by an ultrafilter satisfying certain “genericity” conditions necessitated by the quantifiers), the problem of obtaining a bivalent interpretation reduces to (∗∗) how to obtain a Boolean-valued model from dynamic semantics. Now, [5] attacks (∗∗) using a double-negation translation familiar from Heytingvalued semantics to reconcile two different conceptions of truth in dynamic semantics, and then applies a standard generic model construction for (∗). Although there are perhaps a couple of nice twists in [5], the picture it provides is ultimately unsatisfying because of its semantic limitations: it leaves out the task of repair (or accommodation), which is arguably the difficult (pragmatic) part; and its solution to (∗∗) depends on very strong assumptions about dynamic semantics.

[6] Ambiguity under changing contexts. Presented at Mathematics of Language 4

(Philadelphia), October 1995. To appear in a special issue of Linguistics and Philosophy consisting of selected papers from the conference.

[7] Non-monotonic consequences of preferential contextual disambiguation. In Proceed-

ings, Tenth Amsterdam Colloquium (December 1995), Universiteit van Amsterdam.

[8] Analyzing ambiguity denotationally, operationally and logically. Manuscript, Sep-

tember 1996.

[9] Labeling representations for effective disambiguation (with Nicholas Asher). Pre-

sented in the Second International Workshop on Computational Semantics (Tilburg, The Netherlands), January 1997.

[10] In conjunction with qualitative probability. Manuscript, December 1996.

For, whatever it is that comes first in dynamic semantics, there is no denying that what must come before formal semantics (of which dynamic semantics is an example) is an algorithm transforming a natural language statement into some logical form (fit for, say, model-theoretic analysis).^{3} Such transformations are in general non-trivial; indeed, I believe that intrinsic limits on formalization (of natural language, in its fullest form) preclude the existence of a formal system L of logical forms that would support such a functional transformation. That is,

Thesis A. There is no formal system L such that for every English statement s, there is, up to logical equivalence in L, a unique logical form in L capturing s.

Implicit in Thesis A is the claim that there is a problem — in particular, that

(i) English statements are informal, and hence cannot themselves serve as

the aforementioned logical forms and that

(ii) the binary relation holding between a logical form and an English sentence it “captures” is functional in neither its first nor its second argument.

Given (ii), Thesis A suggests a mismatch between formal and natural languages that smells a lot like ambiguity. A fully precise formulation of Thesis A is, by (i), presumably out of the question, although I think it is enough, as it stands, to convey the message that

(A) ambiguity is a problem that is here to stay. Note that for those who take Church’s thesis seriously, (A) would follow already from a weaker form of Thesis A, in which the universal-existential assertion mentioned can be realized mechanically.

Thesis A′. There is no formal system L and no Turing machine e such that for every English statement s, e returns, on input s, a logical form in L, unique up to logical equivalence in L, capturing s.

3As stressed in Kamp’s recent paper (identified in footnote 1), the DRS construction algorithm is abstracted out of the reformulation of DRT in dynamic semantics.

Missing from either Thesis A or A′ is a reference to context-dependence in discourse interpretation. I have left this out only for the sake of simplicity; the moral would, under a more complicated formulation, be the same: any algorithm taking natural language statements to logical forms must allow for non-determinism — or, in other words, ambiguity. That is not to say that context is unimportant for ambiguity; ambiguity is about nothing if not context. To illustrate this point, suppose an English statement s is “ambiguous” between two non-equivalent logical forms φ and ψ in L. Why not combine φ and ψ into one logical form φ × ψ, where the connective × is, say, disjunction ∨? Many reasons have been advanced in the literature; but for me the simplest and best reply is

(D) what makes an expression ambiguous is the need for disambiguation, and that need is abstracted away when reducing a statement ambiguous between φ and ψ to φ×ψ, for some connective × that (like ∨) requires no more disambiguation than conjunction.^{4}

(D) is the point of departure in [Lca], the conclusion of which is that disambiguation crucially involves contexts — contexts that disambiguate and get disambiguated (the disambiguation in neither case being necessarily total). But what contexts?

This is, of course, a complicated question. Precious little is, I think, to be gained in attacking it in its full glory. The matter becomes more manageable if different notions of context — or (focussing on formal aspects I mentioned at the outset) state — are recognized, roughly according to the familiar semiotic division between syntax, semantics and pragmatics. This plea is made explicit in [Ccp], which asks: are context change potentials functions? In view of the previous paragraph, one might predict that my answer to this somewhat simple-minded query is: no, context change potentials cannot be functions, as non-determinism is required to support ambiguity and indefiniteness (among perhaps a trillion other things). But just as I would not lump the non-determinism in the indefinite noun phrase “a farmer” with ambiguity, neither would I deny the possibility of defining, at a suitable level of abstraction, context change potentials as (partial) functions. There are, I believe, more levels to consider than that of model-theoretic interpretation (with which some would equate formal semantics, fixing contexts to modelembedding pairs). Notable among these levels are, as already mentioned above, those at which logical forms are constructed. Good reasons exist for asserting that logical forms are constructed not only before formal semantics (dynamic or not), but also after and during it. In addition to presupposition, there are postsupposition/implicature and the usual kinds of disambiguation (e.g., anaphora resolution, lexical and structural disambiguation) that require semantic information. These phenomena cry out (to my ear) for logical analysis; some tentative steps in response are taken in [6-10]. Of these papers, I wish to draw the reader’s attention most to [6], which has a few things to say about compositionality and logical consequence in the presence of ambiguity. To bring out natural affinities with theoretical work in computer science, I have also tried a different presentation of [6] in [8]. All proofs have been taken out in [8], although (by way of compensation) [8] includes a few things not in [6]. A basic issue in logical consequence, the acceptability of a conjunction of two acceptable propositions, is explored in [10], a rather technical paper whose connection with ambiguity may seem a bit obscure to the reader unfamiliar with [7]. (By contrast, the relevance of [10] to [Xm] is, I trust, obvious enough.)

4Surely, the union of two sets is no less well-defined than the intersection of two sets is?

And what about the rest of the papers that have found their way into this collection? Despite reservations about the treatment of aspect presupposed there, I have decided to include [3] (a note small enough to slip between the cracks) because it fills a hole in Chapter 5 of Kamp and Reyle’s From Discourse to Logic (Kluwer, 1993). Furthermore, [3] also led me, strangely enough, to [9], which turns to more computationally oriented work on ambiguity, revolving around underspecification. The computational concerns here are far more down-to-earth than in [2], a paper that may strike the reader as odd in the present company. Indeed, [2] was written in a quite different frame of mind, growing out of [Bpl], where an early draft of [2] is mentioned (titled “A path from generalized recursion back to mechanical computation”). Be that as it may, I am convinced that the abstract work on bisimulations described in [Bpl] and [2] is helpful for coming to grips with dynamic semantics. Much more is lurking here than is broached in [Wdr] — including applications to the construct ·_{∀} (presented in [1]) and to ambiguity. Having kept both [Bpl] and [Wdr] out of this collection, I leave [2] in as a hint at these broader applications.

February 11, 1997

Added: March 11, 1997. Delays in printing have made possible the inclusion here of “Processing ambiguity non-deterministically: a modal logic for disambiguation.” (Given another delay, a paper addressing points mentioned above concerning [1] might, with some luck, be ready.)

6 Tim Fernando