Many logical systems today describe intelligent interacting agents over time. Frameworks include Interpreted Systems (IS, Fagin et al. [8]), Epistemic-Temporal Logic (ETL, Parikh & Ramanujam [22]), STIT (Belnap et al. [5]), Process Algebra and Game Semantics (Abramsky [1]). This variety is an asset, as different modeling tools can be fine-tuned to specific applications. But it may also be an obstacle, when barriers between paradigms and schools go up. This paper takes a closer look at one particular interface, between two systems (...) that both address the dynamics of knowledge and information flow in multi-agent systems. One is IS/ETL (IS and ETL are, from a technical point of view, the same up to model transformations, cf. [20]), which uses linear or branching time models with added epistemic structure induced by agents’ different capabilities for observing events. These models provide a Grand Stage where histories of some process unfold constrained by a protocol, and a matching epistemic-temporal language describes what happens. The other framework is Dynamic Epistemic Logic (DEL, [10, 4, 34]) that describes interactive processes in terms of epistemic event models which may occur inside modalities of the language. Temporal evolution is then computed from some initial epistemic model through a process of successive ‘product updates’. It has long been unclear how to best compare IS/ETL and DEL. Various aspects have been investigated in [10, 30, 32], but in this paper, we study the interface in a more systematic way. Often, DEL and ETL are presented as alternative ways of adding dynamics to multi-agent epistemic models. In this paper, we rather focus on how merging the two different modeling choices leads to interesting new questions. Our leading interest here will be a view of informational processes as evolving over time. To see what we mean, consider the simplest version of DEL, viz. the logic of public announcements PAL ([23]) which adds a very specific type of communicative 1 action to epistemic models: a public announcement.. (shrink)

This paper is a brief history of natural logic at the interface of logic, linguistics, and nowadays also other disciplines. It merely summarizes some facts that deserve to be common knowledge.

In the last few years, preference logic and in particular, the dynamic logic of preference change, has suddenly become a live topic in my Amsterdam and Stanford environments. At the request of the editors, this article explains how this interest came about, and what is happening. I mainly present a story around some recent dissertations and supporting papers, which are found in the references. There is no pretense at complete coverage of preference logic (for that, see Hanson 2001) or even (...) of preference change (Hanson 1995). (shrink)

Classical epistemic logic describes implicit knowledge of agents about facts and knowledge of other agents, based on semantic information. The latter is produced by acts of observation or communication, that are described well by dynamic epistemic logics. What these logics do not describe, however, is how significant information is also produced by acts of inference – and key axioms of the system merely postulate “deductive closure”. In this paper, we take the view that all information is produced by acts, and (...) hence we also need a dynamic logic of inference steps showing what effort on the part of the agent makes a conclusion explicit knowledge. Strong omniscience properties of agents should be seen not as static idealizations, but as the result of dynamic processes that agents engage in. This raises two questions: (a) how to define suitable information states of agents and matching notions of explicit knowledge, (b) how to define natural processes over these states that generate new explicit knowledge. To this end, we extend earlier epistemic “awareness models” into a dynamic system that includes acts of public observation, but also adding and dropping formulas from the currently ‘entertained’ set, we give a completeness theorem, and we show how this dynamics updates explicit knowledge. Similar ideas have been proposed before, but they were restricted to update with factual propositions; our new dynamic system applies to arbitrary formulas. We also extend our approach to multi-agent scenarios where awareness changes may happen privately. Finally, we mention further directions and related approaches. (shrink)

Logic is not just about single-agent notions like reasoning, or zero-agent notions like truth, but also about communication between two or more people. What we tell and ask each other can be just as 'logical' as what we infer in Olympic solitude. We show how such interactive phenomena can be studied systematically by merging epistemic and dynamic logic.

Information is a notion of wide use and great intuitive appeal, and hence, not surprisingly, different formal paradigms claim part of it, from Shannon channel theory to Kolmogorov complexity. Information is also a widely used term in logic, but a similar diversity repeats itself: there are several competing logical accounts of this notion, ranging from semantic to syntactic. In this chapter, we will discuss three major logical accounts of information.

Preference is a basic notion in human behaviour, underlying such varied phenomena as individual rationality in the philosophy of action and game theory, obligations in deontic logic (we should aim for the best of all possible worlds), or collective decisions in social choice theory. Also, in a more abstract sense, preference orderings are used in conditional logic or non-monotonic reasoning as a way of arranging worlds into more or less plausible ones. The field of preference logic (cf. Hansson [10]) studies (...) formal systems that can express and analyze notions of preference between various sorts of entities: worlds, actions, or propositions. The art is of course to design a language that combines perspicuity and low complexity with reasonable expressive power. In this paper, we take a particularly simple approach. As preferences are binary relations between worlds, they naturally support standard unary modalities. In particular, our key modality ♦ϕ will just say that is ϕ true in some world which is at least as good as the current one. Of course, this notion can also be indexed to separate agents. The essence of this language is already in [4], but our semantics is more general, and so are our applications and later language extensions. Our modal language can express a variety of preference notions between propositions. Moreover, as already suggested in [9], it can “deconstruct” standard conditionals, providing an embedding of conditional logic into more standard modal logics. Next, we take the language to the analysis of games, where some sort of preference logic is evidently needed ([23] has a binary modal analysis different from ours). We show how a qualitative unary preference modality suffices for defining Nash Equilibrium in strategic games, and also the Backward Induction solution for finite extensive games. Finally, from a technical perspective, our treatment adds a new twist. Each application considered in this paper suggests the need for some additional access to worlds before the preference modality can unfold its true power.. (shrink)

The paper is a discussion of the interpretation of game theory. Game theory is viewed as an abstract inquiry into the concepts used in social reasoning when dealing with situations of conflict and not as an attempt to predict behavior. The first half of the paper..

Current dynamic epistemic logics for analyzing effects of informational events often become cumbersome and opaque when common knowledge is added for groups of agents. Still, postconditions involving common knowledge are essential to successful multi-agent communication. We propose new systems that extend the epistemic base language with a new notion of ‘relativized common knowledge’, in such a way that the resulting full dynamic logic of information flow allows for a compositional analysis of all epistemic postconditions via perspicuous ‘reduction axioms’. We also (...) show how such systems can deal with factual alteration, rather than just information change, making them cover a much wider range of realistic events. After a warm-up stage of analyzing logics for public announcements, our main technical results are expressivity and completeness theorems for a much richer logic that we call LCC. This is a dynamic epistemic logic whose static base is propositional dynamic logic (PDL), interpreted epistemically. This system is capable of expressing all model-shifting operations with finite action models, while providing a compositional analysis for a wide range of informational events. This makes LCC a serious candidate for a standard in dynamic epistemic logic, as we illustrate by analyzing some complex communication scenarios, including sending successive emails with both ‘cc’ and ‘bcc’ lines, and other private announcements to subgroups. Our proofs involve standard modal techniques, combined with a new application of Kleene’s theorem on finite automata, as well as new Ehrenfeucht games of model comparison. (shrink)

The paper presents a study examining the role of working<br>memory in quantifier verification. We created situations similar to the<br>span task to compare numerical quantifiers of low and high rank, parity<br>quantifiers and proportional quantifiers. The results enrich and support<br>the data obtained previously in and predictions drawn from a computational<br>model.

We discuss McMillan et al. (2005) paper devoted to study brain activity during comprehension of sentences with generalized quantifiers. According to the authors their results verify a particular computational model of natural language quantifier comprehension posited by several linguists and logicians (e. g. see van Benthem, 1986). We challenge this statement by invoking the computational difference between first-order quantifiers and divisibility quantifiers (e. g. see Mostowski, 1998). Moreover, we suggest other studies on quantifier comprehension, which can throw more light on (...) the role of working memory in processing quantifiers. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...) Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

We generalize the notion of a monadic algebra to that of a pseudomonadic algebra. In the same way as monadic algebras serve as algebraic models of epistemic modal system S5, pseudomonadic algebras serve as algebraic models of doxastic modal system KD45. The main results of the paper are: Characterization of subdirectly irreducible and simple pseudomonadic algebras, as well as Tokarz's proper filter algebras; Ordertopological representation of pseudomonadic algebras; Complete description of the lattice of subvarieties of the variety of pseudomonadic algebras.

Overview of fundamental work in deontic logic.

Simplicity has long been recognized as an apparent mark of truth in science, but it is difficult to explain why simplicity should be accorded such weight. This chapter examines some standard, statistical explanations of the role of simplicity in scientific method and argues that none of them explains, without circularity, how a reliance on simplicity could be conducive to finding true models or theories. The discussion then turns to a less familiar approach that does explain, in a sense, the elusive (...) connection between simplicity and truth. The idea is that simplicity does not point at or reliably indicate the truth but, rather, keeps inquiry on the cognitively most direct path to the truth. (shrink)

Examines the link between nonmonotonic inference relations and theory revision operations, focusing on the correspondence between abstract properties which each may satisfy.

Psychological experirnents have repeatedly shown that in judging the likelihood of uncertain events people do not follow the principles of probability theory. A notorious example is given by the so called conjunction fallacy. In this paper I argue that this fallacy is not really a fallacy when it is analysed in the light of a dynamic theory of default reasoning. The question that immediately rises is whether the fact that this theory conforms better to the way people actually think provides (...) a reason to prefer it to probability theory. (shrink)

A well-known open problem in epistemic logic is to give a syntactic characterization of the successful formulas. Semantically, a formula is successful if and only if for any pointed model where it is true, it remains true after deleting all points where the formula was false. The classic example of a formula that is not successful in this sense is the “Moore sentence” p ∧ ¬BOXp, read as “p is true but you do not know p.” Not only is the (...) Moore sentence unsuccessful, it is self-refuting, for it never remains true as described. We show that in logics of knowledge and belief for a single agent (extended by S5), Moorean phenomena are the source of all self-refutation; moreover, in logics for an introspective agent (extending KD45), Moorean phenomena are the source of all unsuccessfulness as well. This is a distinctive feature of such logics, for with a non-introspective agent or multiple agents, non-Moorean unsuccessful formulas appear. We also consider how successful and self-refuting formulas relate to the Cartesian and learnable formulas, which have been discussed in connection with Fitch’s “paradox of knowability.” We show that the Cartesian formulas are exactly the formulas that are not eventually self-refuting and that not all learnable formulas are successful. In an appendix, we give syntactic characterizations of the successful and the self-refuting formulas. (shrink)

This paper works within a particular framework for reasoning about actions—sometimes known as the framework of “stit semantics”—originally due to Belnap and Perloff, based ultimately on the theory of indeterminism set out in Prior’s indeterministic tense logic, and developed in full detail by Belnap, Perloff, and Xu [3]. The issues I want to consider arise when certain normative, or decision theoretic, notions are introduced into this framework: here I will focus on the notion of a right action, and so on (...) the formulation of act utilitarianism within this indeterministic setting. The problem is simply that there are two different, and conflicting, ways of defining this notion, both well-motivated, and both carrying intuitive weight. (shrink)

Quillen [17] introduced model categories as an abstract framework for homotopy theory which would apply to a wide range of mathematical settings. By all accounts this program has been a success and—as, e.g., the work of Voevodsky on the homotopy theory of schemes [15] or the work of Joyal [11, 12] and Lurie [13] on quasicategories seem to indicate—it will likely continue to facilitate mathematical advances. In this paper we present a novel connection between model categories and mathematical logic, inspired (...) by the groupoid model of (intensional) Martin–Löf type theory [14] due to Hofmann and Streicher [9]. In particular, we show that a form of Martin–Löf type theory can be soundly modelled in any model category. This result indicates moreover that any model category has an associated “internal language” which is itself a form of Martin-Löf type theory. This suggests applications both to type theory and to homotopy theory. Because Martin–Löf type theory is, in one form or another, the theoretical basis for many of the computer proof assistants currently in use, such as Coq and Agda (cf. [3] and [5]), this promise of applications is of a practical, as well as theoretical, nature. This paper provides a precise indication of this connection between homotopy theory and logic; a more detailed discussion of these and further results will be given in [20]. (shrink)

Restricting attention to the class of extensive games defined by von Neumann and Morgenstern with the added assumption of perfect recall, we specify the information of each player at each node of the game-tree in a way which is coherent with the original information structure of the extensive form. We show that this approach provides a framework for a formal and rigorous treatment of questions of knowledge and common knowledge at every node of the tree. We construct a particular information (...) partition for each player and show that it captures the notion of maximum information in the sense that it is the finest within the class of information partitions that satisfy four natural properties. Using this notion of “maximum information” we are able to provide an alternative characterization of the meet of the information partitions. (shrink)

This essay is structured around the bifurcation between proofs and models: The first section discusses Proof Theory of relevant and substructural logics, and the second covers the Model Theory of these logics. This order is a natural one for a history of relevant and substructural logics, because much of the initial work — especially in the Anderson–Belnap tradition of relevant logics — started by developing proof theory. The model theory of relevant logic came some time later. As we will see, (...) Dunn’s algebraic models [76, 77] Urquhart’s operational semantics [267, 268] and Routley and Meyer’s relational semantics [239, 240, 241] arrived decades after the initial burst of activity from Alan Anderson and Nuel Belnap. The same goes for work on the Lambek calculus: although inspired by a very particular application in linguistic typing, it was developed first proof-theoretically, and only later did model theory come to the fore. Girard’s linear logic is a different story: it was discovered though considerations of the categorical models of coherence.. (shrink)

This is one of the seminal articles of the pragmatist tradition where C.S. Peirce sets out his doctrine of doubt and belief --and their relationship to inquiry and clarity of our concepts. Originally published in the Popular Science Monthly; and widely available in reprints and collections of Peirce's writings.

The notion of perfect recall in extensive games was introduced by Kuhn (1953), who interpreted it as "equivalent to the assertion that each player is allowed by the rules of the game to remember everything he knew at previous moves and all of his choices at those moves''. We provide a characterization and axiomatization of perfect recall based on two notions of memory: (1) memory of past knowledge and (2) memory of past actions.