Logical frameworks for analysing the dynamics ofinformation processing abound [4, 5, 8, 10, 12, 14, 20, 22]. Some of these frameworks focus on the dynamics of the interpretation process, some on the dynamics of the process of drawing inferences, and some do both of these. Formalisms galore, so it is felt that some conceptual streamlining would pay off. This paper is part of a larger scale enterprise to pursue the obvious parallel between information processing and imperative programming. We demonstrate that (...) logical tools from theoretical computer science are relevant for the logic of information flow. More specifically, we show that the perspective of bare logic [13, 18] can fruitfully be applied to the conceptual simplification of information flow logics. Part one of this program consisted of the analysis of 'dynamic interpretation' in this way, using the example of dynamic predicate logic [10]; the results were published in [7]. The present paper constitutes the second part of the program, the analysis of 'dynamic inference'. Here we focus on Veltman’s update logic [22]. Update logic is an example of a logical framework which takes the dynamics of drawing inferences into account by modelling information growth as discarding of possibilities. This paper shows how information logics like update logic can fruitfully be studied by linking their dynamic principles to static 'correctness descriptions'. Our theme is exemplified by providing a sound and complete HoarelPratt style deduction system for update logic. The Hoare/Pratt correctness statements use modal propositional dynamic logic as assertion language and connect update logic to the modal propositional logic S5. The connection with S5 provides a clear link between the dynamic and the static semantics of update logic. The fact that update logic is decidable was noted already in [2]; the connection with S5 provides an alternative proof. The S5 connection can also be used for rephrasing the validity notions of update logic and for performing consistency checks. In conclusion, it is argued that interpreting the dynamic statements of information logics as dynamic modal operators has much wider applicability. In fact, the method can be used to axiomatize quite a wide range of information logics. (shrink)

The aim of this paper is twofold: (i) to introduce the framework of update semantics and to explain what kind of semantic phenomena may successfully be analysed in it: (ii) to give a detailed analysis of one such phenomenon: default reasoning.

Logical frameworks for analysing the dynamics of information processing abound [4, 5, 8, 10, 12, 14, 20, 22]. Some of these frameworks focus on the dynamics of the interpretation process, some on the dynamics of the process of drawing inferences, and some do both of these. Formalisms galore, so it is felt that some conceptual streamlining would pay off.This paper is part of a larger scale enterprise to pursue the obvious parallel between information processing and imperative programming. We demonstrate that (...) logical tools from theoretical computer science are relevant for the logic of information flow. More specifically, we show that the perspective of Hoare logic [13, 18] can fruitfully be applied to the conceptual simplification of information flow logics. (shrink)

A variety of logical frameworks have been developed to study rational agents interacting over time. This paper takes a closer look at one particular interface, between two systems that both address the dynamics of knowledge and information flow. The first is Epistemic Temporal Logic (ETL) which uses linear or branching time models with added epistemic structure induced by agents’ different capabilities for observing events. The second framework is Dynamic Epistemic Logic (DEL) that describes interactive processes in terms of epistemic event (...) models which may occur inside modalities of the language. This paper systematically and rigorously relates the DEL framework with the ETL framework. The precise relationship between DEL and ETL is explored via a new representation theorem characterizing the largest class of ETL models corresponding to DEL protocols in terms of notions of Perfect Recall , No Miracles , and Bisimulation Invariance . We then focus on new issues of completeness . One contribution is an axiomatization for the dynamic logic of public announcements constrained by protocols, which has been an open problem for some years, as it does not fit the usual ‘reduction axiom’ format of DEL. Finally, we provide a number of examples that show how DEL suggests an interesting fine-structure inside ETL. (shrink)

We investigate the semantics of messages, and argue that the meaning ofa message is naturally and usefully given in terms of how it affects theknowledge of the agents involved in the communication. We note thatthis semantics depends on the protocol used by the agents, and thus not only the message itself, but also the protocol appears as a parameter in the meaning. Understanding this dependence allows us to give formal explanations of a wide variety of notions including language dependence, implicature, (...) and the amount of information in a message. (shrink)

Dynamic Epistemic Logic is the logic of knowledge change. This book provides various logics to support such formal specifications, including proof systems. Concrete examples and epistemic puzzles enliven the exposition. The book also offers exercises with answers. It is suitable for graduate courses in logic. Many examples, exercises, and thorough completeness proofs and expressivity results are included. A companion web page offers slides for lecturers and exams for further practice.

Reasoning About Knowledge is the first book to provide a general discussion of approaches to reasoning about knowledge and its applications to distributed ...

Dynamic Epistemic Logic This article tells the story of the rise of dynamic epistemic logic, which began with epistemic logic, the logic of knowledge, in the 1960s. Then, in the late 1980s, came dynamic epistemic logic, the logic of change of knowledge. Much of it was motivated by puzzles and paradoxes. The number … Continue reading Dynamic Epistemic Logic →.

Dynamic Epistemic Logic This article tells the story of the rise of dynamic epistemic logic, which began with epistemic logic, the logic of knowledge, in the 1960s. Then, in the late 1980s, came dynamic epistemic logic, the logic of change of knowledge. Much of it was motivated by puzzles and paradoxes. The number … Continue reading Dynamic Epistemic Logic →.

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)

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)