The AGM paradigm of belief change studies the dynamics of belief states in light of new information. Finding, or even approximating, those beliefs that are dependent on or relevant to a change is valuable because, for example, it can narrow the set of beliefs considered during belief change operations. A strong intuition in this area is captured by Gärdenfors’s preservation criterion (GPC), which suggests that formulas independent of a belief change should remain intact. GPC thus allows one to build dependence relations that are linked with belief change. Such dependence relations can in turn be used as a theoretical benchmark against which to evaluate other approximate dependence or relevance relations. Fariñas and Herzig axiomatize a dependence relation with respect to a belief set, and, based on GPC, they characterize the correspondence between AGM contraction functions and dependence relations. In this paper, we introduce base dependence as a relation between formulas with respect to a belief base, and prove a more general characterization that shows the correspondence between kernel contraction and base dependence. At this level of generalization, different types of base dependence emerge, which we show to be a result of possible redundancy in the belief base. We further show that one of these relations that emerge, strong base dependence, is parallel to saturated kernel contraction. We then prove that our latter characterization is a reversible generalization of Fariñas and Herzig’s characterization. That is, in the special case when the underlying belief base is deductively closed (i.e., it is a belief set), strong base dependence reduces to dependence, and so do their respective characterizations. Finally, an intriguing feature of Fariñas and Herzig’s formalism is that it meets other criteria for dependence, namely, Keynes’s conjunction criterion for dependence (CCD) and Gärdenfors’s conjunction criterion for independence (CCI). We prove that our base dependence formalism also meets these criteria. Even more interestingly, we offer a more specific criterion that implies both CCD and CCI, and show our base dependence formalism also meets this new criterion.

Mass terms are those such as ‘water’, ‘computer software’, ‘advice’, and ‘knowledge’. They are contrasted with count terms such as ‘person’, ‘computer program’, ‘suggestion’, and ‘belief’. Intuitively, mass terms refer to “stuff” while count terms refer to “objects”. Since mass terms refer to stuff, they (but not count terms) allow for measurement: ‘a liter of water’, ‘three CDs worth of computer software’, ‘too much advice’, ‘many books worth of deep knowledge’. Since count terms refer to objects, they (but not mass terms) allow for counting, quantifying and individuating: ‘a person’, ‘three computer programs’, ‘each suggestion’, ‘that belief of his’.

In this paper we explore a class of belief update operators, in which the definition of the operator is compositional with respect to the sentence to be added. The goal is to provide an update operator that is intuitive, in that its definition is based on a recursive decomposition of the update sentence's structure, and that may be reasonably implemented. In addressing update, we first provide a definition phrased in terms of the models of a knowledge base. While this operator satisfies a core group of the benchmark Katsuno-Mendelzon update postulates, not all of the postulates are satisfied. Other Katsuno-Mendelzon postulates can be obtained by suitably restricting the syntactic form of the sentence for update, as we show. In restricting the syntactic form of the sentence for update, we also obtain a hierarchy of update operators with Winslett's standard semantics as the most basic interesting approach captured. We subsequently give an algorithm which captures this approach; in the general case the algorithm is exponential, but with some not-unreasonable assumptions we obtain an algorithm that is linear in the size of the knowledge base. Hence the resulting approach has much better complexity characteristics than other operators in some situations. We also explore other compositional belief change operators: erasure is developed as a dual operator to update; we show that a forget operator is definable in terms of update; and we give a definition of the compositional revision operator. We obtain that compositional revision, under the most natural definition, yields the Satoh revision operator.

Computational semantics is the study of how to represent meaning in a way that computers can use.For the authors of this textbook, this study includes the representation of the meaning of natural language in logic formalisms, the recognition of certain relations that hold within this formalization (such as synonymy, consistency, and implication), and the computational implementation of all this.I think that, while there probably are not many courses devoted to computational semantics, this book could profitably be incorporated into more traditional computational linguistics courses, especially when two courses are offered serially.The material here could be spread out and integrated into parts of a more standard pair of these courses, and it would result in a substantial widening of the knowledge that students come away with from these courses.The introduction of this book traces the history of computational semantics, with a goal of justifying the enterprise in the face of the modern emphasis on statistical natural language processing.Besides this introduction, the book contains six substantial chapters and four short appendices.There is also a very extensive suite of material online at a Web site maintained by the authors.Chapter 1 is an introduction to first-order logic, but with a twist that underscores the particular outlook taken in this book.There is a very short introduction to the notion of a model of a set of quantifier-free sentences, followed by an equally short discussion of the interpretation of quantifiers in a model.With respect to quantifier-free sentences, students are referred to the three-page Appendix B on propositional logic, where truth-tables are covered.The innovations start with the introduction of three "inference tasks": querying, consistency checking, and informativity checking.These correspond to the logical concepts of satisfiability (of a given formula in a given model), consistency (whether there is a model that satisfies a given formula), and validity (whether a formula is true in all models, or, equivalently, whether a given argument is valid).Although the notions of querying, etc., are thus merely renamings of standard logical notions, it seems to me that the renaming is particularly apposite in the setting of a textbook for non-logicians, especially since much is to be done computationally with these notions in the enterprise of computational semantics.Much of the remainder of chapter 1 consists of a gentle introduction to Prolog and using it to check formulas for well-formedness and to build model checkers with the goal of implementing the querying task.

This is a position paper concerning the role of empirical studies of human default reasoning in the formalization of AI theories of default reasoning. We note that AI motivates its theoretical enterprise by reference to human skill at default reasoning, but that the actual research does not make any use of this sort of information and instead relies on intuitions of individual investigators. We discuss two reasons theorists might not consider human performance relevant to formalizing default reasoning: (a) that intuitions are sufficient to describe a model, and (b) that human performance in this arena is irrelevant to a competence model of the phenomenon. We provide arguments against both these reasons. We then bring forward three further considerations against the use of intuitions in this arena: (a) it leads to an unawareness of predicate ambiguity, (b) it presumes an understanding of ordinary language statements of typicality, and (c) it is similar to discredited views in other fields. We advocate empirical investigation of the range of human phenomena that intuitively embody default reasoning. Gathering such information would provide data with which to generate formal default theories and against which to test the claims of proposed theories. Our position is that such data are the very phenomena that default theories are supposed to explain.

There are various difficulties in accomodating the traditional mass/count distinction into a grammar for English which has a goal the production of "logical form" semantic translations of the initial English sentences. The present paper surveys some of these difficulties. One puzzle is whether the distinction is a syntactic one or a semantic one, i.e., whether it is a well-formedness constraint or whether it is a description of the semantic translations produced. Another puzzle is whether it should be applied to simple words (as they occur in the lexicon) or whether it should apply only to longer units (such as entire NPs). Of the wide variety of possible theories, only two seem to produce the required results (having to do with plausible inferences and intuitively satisfying semantic representations). These two theories are developed and compared.