This book provides the first comprehensive introduction to Dynamic Logic. Among the many approaches to formal reasoning about programs, Dynamic Logic enjoys the singular advantage of being strongly related to classical logic. Its variants constitute natural generalizations and extensions of classical formalisms. For example, Propositional Dynamic Logic (PDL) can be described as a blend of three complementary classical ingredients: propositional calculus, modal logic, and the algebra of regular events. In First-Order Dynamic Logic (DL), the propositional calculus is replaced by classical (...) first-order predicate calculus. Dynamic Logic is a system of remarkable unity that is theoretically rich as well as of practical value. It can be used for formalizing correctness specifications and proving rigorously that those specifications are met by a particular program. Other uses include determining the equivalence of programs, comparing the expressive power of various programming constructs, and synthesizing programs from specifications. This book provides the first comprehensive introduction to Dynamic Logic. It is divided into three parts. The first part reviews the appropriate fundamental concepts of logic and computability theory and can stand alone as an introduction to these topics. The second part discusses PDL and its variants, and the third part discusses DL and its variants. Examples are provided throughout, and exercises and a short historical section are included at the end of each chapter. (shrink)

Preface This book is about semantics and logic. More specifically, it is about the semantics and logic of natural language; and, even more specifically than ...

and Data The essence of scope in natural language semantics can be characterized as follows: an expression e1 takes scope over an expression e2 iff the interpretation of the former affects the interpretation of the latter. Consider, for example, the sentence in (1) below, which is typical of the cases discussed in this paper in that it involves an indefinite and a universal (or, more generally, a non-existential) quantifier. (1) Everyx student in my class read ay paper about scope. How (...) can we tell whether the indefinite in (1) is in the scope of the universal or not? We can answer this question in two ways. From a dependence-based perspective, Q y is in the scope of Qx if the values of the variable y (possibly) covary with the values of x. From an independence-based perspective, Q y is outside the scope of Qx if y’s value is fixed relative to the values of x. This brings us to the first of our two central questions: should the scopal properties of ordinary, ‘unmarked’ indefinites be characterized in terms of dependence or in terms of independence? The difference between these two conceptualizations is that a dependence-based approach establishes which quantifier(s) Q y is dependent on, while an independence-based approach establishes which quantifier(s) Q y is independent of. Logical semantics has taken both paths to the notion of scope: compare the standard, dependence-based semantics of first-order logic (FOL) – or the dependence-driven Skolemization procedure – with the independence-based semantics of Independence-Friendly Logic (IFL, Hintikka 1973, Sandu 1993, Hodges 1997, Väänänen 2007 among others). Natural language semantics has only taken the dependence-based path. (shrink)

I LOGIC IN PHILOSOPHY— PHILOSOPHY OF LOGIC i. On the relation of logic to philosophy I n this book, the consequences of certain logical insights for ...

CHAPTER 1. INTENSIONAL LOGIC §1. Natural Language and Intensional Logic When we speak of a theory of meaning for a natural language such as English, ...

Over the last twenty years, in all of these neighbouring fields, modal systems have been developed that we call multi-dimensional. (Our definition of multi ...

In The Dynamics of Meaning , Gennaro Chierchia tackles central issues in dynamic semantics and extends the general framework. Chapter 1 introduces the notion of dynamic semantics and discusses in detail the phenomena that have been used to motivate it, such as "donkey" sentences and adverbs of quantification. The second chapter explores in greater depth the interpretation of indefinites and issues related to presuppositions of uniqueness and the "E-type strategy." In Chapter 3, Chierchia extends the dynamic approach to the domain (...) of syntactic theory, considering a range of empirical problems that includes backwards anaphora, reconstruction effects, and weak crossover. The final chapter develops the formal system of dynamic semantics to deal with central issues of definites and presupposition. Chierchia shows that an approach based on a principled enrichment of the mechanisms dealing with meaning is to be preferred on empirical grounds over approaches that depend on an enrichment of the syntactic apparatus. Dynamics of Meaning illustrates how seemingly abstract stances on the nature of meaning can have significant and far-reaching linguistic consequences, leading to the detection of new facts and influencing our understanding of the syntax/semantics/pragmatics interface. (shrink)

The paper proposes an account of the contrast (noticed in Karttunen 1976) between the interpretations of the following two discourses: Harvey courts a girl at every convention. {She is very pretty. vs. She always comes to the banquet with him.}. The initial sentence is ambiguous between two quantifier scopings, but the first discourse as a whole allows only for the wide-scope indefinite reading, while the second allows for both. This cross-sentential interaction between quantifier scope and anaphora is captured by means (...) of a new dynamic system couched in classical type logic, which extends Compositional DRT (Muskens 1996) with plural information states (modeled, following van den Berg 1996, as sets of variable assignments). Given the underlying type logic, compositionality at sub-clausal level follows automatically and standard techniques from Montague semantics become available. The paper also shows that modal subordination (A wolf might come in. It would eat Harvey first) can be analyzed in a parallel way, i.e. the system captures the anaphoric and quantificational parallels between the individual and modal domains argued for in Stone (1999) (among others). In the process, we see that modal / individual-level quantifiers enter anaphoric connections as a matter of course, usually functioning simultaneously as both indefinites and pronouns. (shrink)

We shall introduce in this paper a language whose formulas will be interpreted by games of imperfect information. Such games will be defined in the same way as the games for first-order formulas except that the players do not have complete information of the earlier course of the game. Some simple logical properties of these games will be stated together with the relation of such games of imperfect information to higher-order logic. Finally, a set of applications will be outlined.

This paper is devoted to the formulation and investigation of a dynamic semantic interpretation of the language of first-order predicate logic. The resulting system, which will be referred to as ‘dynamic predicate logic’, is intended as a first step towards a compositional, non-representational theory of discourse semantics. In the last decade, various theories of discourse semantics have emerged within the paradigm of model-theoretic semantics. A common feature of these theories is a tendency to do away with the principle of compositionality, (...) a principle which, implicitly or explicitly, has dominated semantics since the days of Frege. Therefore the question naturally arises whether non-compositionality is in any way a necessary feature of discourse semantics. Since we subscribe to the interpretation of compositionality as constituting primarily a methodological principle, we consider this to be a methodological rather than an empirical question. As a consequence, the emphasis in the present paper lies on developing an alternative compositional semantics of discourse, which is empirically equivalent to its non-compositional brethren, but which differs from them in a principled methodological way. Hence, no attempts are made to improve on existing theories empirically. Nevertheless, as we indicate in section 5, the development of a compositional alternative may in the end have empirical consequences, too. First of all, it can be argued that the dynamic view on interpretation developed in this paper suggests natural and relatively easy to formulate extensions which enable one to deal with a wider range of phenomena than can be dealt with in existing theories. Moreover, the various approaches to the model-theoretic semantics of discourse that have been developed during the last decade, have constituted a ‘fresh start’ in the sense that much of what had been accomplished before was ignored, at least for a start. Of course, this is a justified strategy if one feels one is trying to develop a radically different approach to recalcitrant problems. However, there comes a time when such new approaches have to be compared with the older one, and when an assessment of the pros and cons of each has to be made. One of the main problems in semantics today, we feel, is that a semantic theory such as Montague grammar, and an approach like Kamp’s discourse representation theory, are hard to compare, let alone that it is possible to unify their insights and results.. (shrink)

The formal semantics that we have proposed for definite and indefinite descriptions analyzes them both as variable-binding operators and as referring terms. It is the referential analysis which makes it possible to account for the facts outlined in Section 2, e.g. for the purely ‘instrumental’ role of the descriptive content; for the appearance of unusually wide scope readings relative to other quantifiers, higher predicates, and island boundaries; for the fact that the island-escaping readings are always equivalent to maximally wide scope (...) quantifiers; and for the appearance of violations of the identity conditions on variables in deleted constituents. We would emphasize that this is not a random collection of observations. They cohere naturally with each other, and with facts about other phrases that are unambigously referential.We conceded at the outset of this paper that the referential use of an indefinite noun phrase does not, by itself, motivate the postulation of a referential interpretation. Our argument has been that the behavior of indefinites in complex sentences cannot be economically described, and certainly cannot be explained, unless a referential interpretation is assumed. It could be accounted for in pragmatic terms only if the whole theory of scope relations and of conditions on deletion could be eliminated from the semantics and incorporated into a purely pragmatic theory. But this seems unlikely. (shrink)

The purpose of this paper is to (a) show that the received view of the problem of quantificational subordination (QS) is incorrect, and that, consequently, existing solutions do not succeed in explaining the facts, and (b) provide a new account of QS. On the received view of QS within dynamic semantic frameworks, determiners treated as universal quantifiers (henceforth universal determiners) such as all, every, and each behave as barriers to inter-sentential anaphora yet allow anaphoric accessibility in a number of situations. (...) We argue that universal determiners are not intrinsic anaphora barriers and that anaphoric accessibility under them is enabled factors including lexicon information and discourse effects of universal determiners. In support of this viewpoint, we first provide a data survey on the phenomena of QS and its interactions with plurals, rhetorical relations, and adverbial quantification. The results of the survey show that judgments of (naive) native English speakers on the QS examples are quite different from what is claimed in the literature. We argue that the various solutions in the literature, which in general accept that universal determiners are intrinsic anaphora barriers, fail to account for the facts from the survey data. We then describe the approach we adopt, which denies that universal determiners are anaphora barriers and reconstructs their semantics so that information in their scope can be released for anaphora. The constraints on QS noted in the literature we model in Segmented Discourse Representation Theory (SDRT) as conditions on the discourse relations which can hold between subordinated constituents. We show that this approach accounts for the QS data. (shrink)

This paper introduces a framework for direct surface composition by online update. The surface string is interpreted as is, with each morpheme in turn updating the input state of information and attention. A formal representation language, Logic of Centering, is defined and some crosslinguistic constraints on lexical meanings and compositional operations are formulated.

I propose the first strictly compositional semantic account of same. New data, including especially NP-internal uses such as two men with the same name, suggests that same in its basic use is a quantificational element taking scope over nominals. Given type-lifting as a generally available mechanism, I show that this follows naturally from the fact that same is an adjective. Independently-motivated assumptions extend the analysis to standard examples such as Anna and Bill read the same book via a mechanism I (...) call PARASITIC SCOPE, in which the scope of same depends on the scope of some other scopetaking element in the sentence. Although I will initially discuss the analysis in terms of a familiar Quantifier Raising framework, I go on to implement the analysis within an innovative continuation-based Type-Logical Grammar. The empirical payoff for dealing in continuations is that a simple generalization of the basic analysis gives the first ever formal account of cases in which same distributes over objects other than NP denotations, as in the relevant interpretation of John hit and killed the same man. (shrink)

We describe a logic which is the same as first-order logic except that it allows control over the information that passes down from formulas to subformulas. For example the logic is adequate to express branching quantifiers. We describe a compositional semantics for this logic; in particular this gives a compositional meaning to formulas of the 'information-friendly' language of Hintikka and Sandu. For first-order formulas the semantics reduces to Tarski's semantics for first-order logic. We prove that two formulas have the same (...) interpretation in all structures if and only if replacing an occurrence of one by an occurrence of the other in a sentence never alters the truth-value of the sentence in any structure. (shrink)

Quantification is a topic which brings together linguistics, logic, and philosophy. Quantifiers are the essential tools with which, in language or logic, we refer to quantity of things or amount of stuff. In English they include such expressions as no, some, all, both, many. Peters and Westerstahl present the definitive interdisciplinary exploration of how they work - their syntax, semantics, and inferential role.

The paper proposes the first unified account of deictic/sentence-external and sentence-internal readings of singular different . The empirical motivation for such an account is provided by a cross-linguistic survey and an analysis of the differences in distribution and interpretation between singular different , plural different and same (singular or plural) in English. The main proposal is that distributive quantification temporarily makes available two discourse referents within its nuclear scope, the values of which are required by sentence-internal uses of singular different (...) to be distinct, much as its deictic uses require the values of two discourse referents to be distinct. Thus, we take sentence-internal readings to be a form of ‘association with distributivity’ that is similar to association with focus. The contrast between singular different , plural different and same is explained in terms of several kinds of quantificational distributors that license their internal readings. The analysis is executed in a stack-based dynamic system couched in type logic, so we get compositionality in the usual Montagovian way. Quantificational subordination and dependent indefinites in various languages provide additional motivation for the account. Investigating the connections between items with sentence-internal readings and the quantificational licensors of these readings opens up a larger project of formally investigating (i) the typology of quantificational distributors and distributivity-dependent items and (ii) the fine-grained contexts of evaluation needed to capture this typological variation. (shrink)

Partee (1973) noted anaphoric parallels between English tenses and pronouns. Since then these parallels have been analyzed in terms of type-neutral principles of discourse anaphora. Recently, Stone (1997) extended the anaphoric parallel to English modals. In this paper I extend the story to languages of other types. This evidence also shows that centering parallels are even more detailed than previously recognized. Based on this evidence, I propose a semantic representation language (Logic of Change with Centered Worlds), in which the observed (...) parallels can be formally analyzed. (shrink)

Dependence is a common phenomenon, wherever one looks: ecological systems, astronomy, human history, stock markets - but what is the logic of dependence? This book is the first to carry out a systematic logical study of this important concept, giving on the way a precise mathematical treatment of Hintikka’s independence friendly logic. Dependence logic adds the concept of dependence to first order logic. Here the syntax and semantics of dependence logic are studied, dependence logic is given an alternative game theoretic (...) semantics, and results about its complexity are proven. This is a graduate textbook suitable for a special course in logic in mathematics, philosophy and computer science departments, and contains over 200 exercises, many of which have a full solution at the end of the book. It is also accessible to readers, with a basic knowledge of logic, interested in new phenomena in logic. (shrink)

In the tradition of quantified modal logic, it was assumed that significantly different linguistic systems underlie reference to individuals, to times and to 'possible worlds'. Various results from recent research in formal semantics suggest that this is not so, and that there is in fact a pervasive symmetry between the linguistic means with which we refer to these three domains. Reference to individuals, times and worlds is uniformly effected through generalized quantifiers, definite descriptions, and pronouns, and in each domain grammatical (...) features situate the reference of terms as near, far or 'further' from the actual or from a reported speech act. We outline various directions in which a program of ontological symmetry could be developed, and we offer in the Appendix a symmetric fragment developed in a logic that can be seen as a compromise between an extensional and an intensional system. (shrink)

This paper embeds the core part of Discourse Representation Theory in the classical theory of types plus a few simple axioms that allow the theory to express key facts about variables and assignments on the object level of the logic. It is shown how the embedding can be used to combine core analyses of natural language phenomena in Discourse Representation Theory with analyses that can be obtained in Montague Semantics.

This paper claims that indefinite descriptions, singular and plural, have different scope properties than genuine quantifiers. This claim is based on their distinct behavior in island constructions: while indefinites in islands can have intermediate (and maximal) scope readings, quantifiers cannot. Further, the simplest in situ interpretation strategy for indefinites results in incorrect truth conditions for intermediate (and maximal) scope readings. I introduce a mechanism which “auto-matically” preserves the restriction on free variables corresponding to indefinites, in a way which allows the (...) restriction to be carried up in the course of semantic interpretation and to be used at the level where the variable is quantified. This mechanism is a realization of the “indefinites-as-free-variables” proposal of Lewis, Kamp, and Heim, but emphasizes the role of the restriction. I then show that distributive readings of plural indefinites also display island-escaping behavior and argue for an independent, island-insensitive distribution mechanism. (shrink)

In this paper, I show that the availability of what some authors have called the weak reading and the strong reading of donkey sentences with relative clauses is systematically related to monotonicity properties of the determiner. The correlation is different from what has been observed in the literature in that it concerns not only right monotonicity, but also left monotonicity (persistence/antipersistence). I claim that the reading selected by a donkey sentence with a double monotone determiner is in fact the one (...) that validates inference based on the left monotonicity of the determiner. This accounts for the lack of strong reading in donkey sentences with MON determiners, which have been neglected in the literature. I consider the relevance of other natural forms of inference as well, but also suggest how monotonicity inference might play a central role in the actual process of interpretation. The formal theory is couched in dynamic predicate logic with generalized quantifiers. (shrink)

The paper argues that two distinct and independent notions of plurality are involved in natural language anaphora and quantification: plural reference (the usual non-atomic individuals) and plural discourse reference, i.e., reference to a quantificational dependency between sets of objects (e.g., atomic/non-atomic individuals) that is established and subsequently elaborated upon in discourse. Following van den Berg (PhD dissertation, University of Amsterdam, 1996), plural discourse reference is modeled as plural information states (i.e., as sets of variable assignments) in a new dynamic system (...) couched in classical type logic that extends Compositional DRT (Muskens, Linguistics and Philosophy, 19, 143-186, 1996). Given the underlying type logic, compositionality at sub-clausal level follows automatically and standard techniques from Montague semantics become available. The idea that plural info states are semantically necessary (in addition to non-atomic individuals) is motivated by relative-clause donkey sentences with multiple instances of singular donkey anaphora that have mixed (weak and strong) readings. At the same time, allowing for non-atomic individuals in addition to plural info states enables us to capture the intuitive parallels between singular and plural (donkey) anaphora, while deriving the incompatibility between singular (donkey) anaphora and collective predicates. The system also accounts for empirically unrelated phenomena, e.g., the uniqueness effects associated with singular (donkey) anaphora discussed in Kadmon (Linguistics and Philosophy, 13, 273-324, 1990) and Heim (Linguistics and Philosophy, 13, 131-177, 1990) among others. (shrink)

In modal subordination, a modal sentence is interpreted relative to a hypothetical scenario introduced in an earlier sentence. In this paper, I argue that this phenomenon reflects the fact that the interpretation of modals is an ANAPHORIC process. Modal morphemes introduce sets of possible worlds, representing alternative hypothetical scenarios, as entities into the discourse model. Their interpretation depends on evoking sets of worlds recording described and reference scenarios, and relating such sets to one another using familiar notions of restricted, preferential (...) quantification. This proposal relies on an extended model of environments in dynamic semantics to keep track of associations between possible worlds and ordinary individuals; it assumes that modal meanings and other lexical meanings encapsulate quantification over possible worlds. These two innovations are required in order for modals to refer to sets of possible worlds directly as static objects in place of the inherently dynamic objects—quite different from the referents of pronouns and tenses—used in previous accounts. The simpler proposal that results offers better empirical coverage and suggests a new parallel between modal and temporal interpretation. (shrink)

The paper investigates the scope properties of indefinites.

The complexity of any logical modeling reflects both the intrinsic structure of a topic described and the weight of the formal tools. Some of this weight seems inherent in even the most basic logical systems. Notably, standard predicate logic is undecidable. In this paper, we investigate ‘lighter’ versions of this general purpose tool, by modally ‘deconstructing’ the usual semantics, and locating implicit choice points in its set up. The first part sets out the interest of this program and the modal (...) techniques employed, while the second part provides technical elaborations demonstrating its viability. (shrink)