In this paper, we present several extensions of epistemic logic with update operators modelling public information change. Next to the well-known public announcement operators, we also study public substitution operators. We prove many of the results regarding expressivity and completeness using so-called reduction axioms. We develop a general method for using reduction axioms and apply it to the logics at hand.

In ‘belief revision’ a theory is revised with a formula φ resulting in a revised theory . Typically, is in , one has to give up belief in by a process of retraction, and φ is in . We propose to model belief revision in a dynamic epistemic logic. In this setting, we typically have an information state (pointed Kripke model) for the theory wherein the agent believes the negation of the revision formula, i.e., wherein is true. The revision with (...) φ is a program *φ that transforms this information state into a new information state. The transformation is described by a dynamic modal operator [*φ], that is interpreted as a binary relation [ [*φ] ] between information states. The next information state is computed from the current information state and the belief revision formula. If the revision is successful, the agent believes φ in the resulting state, i.e., Bφ is then true. To make this work, as information states we propose ‘doxastic epistemic models’ that represent both knowledge and degrees of belief. These are multi-modal and multi-agent Kripke models. They are constructed from preference relations for agents, and they satisfy various characterizable multi-agent frame properties. Iterated, revocable, and higher-order belief revision are all quite natural in this setting. We present, for an example, five different ways of such dynamic belief revision. One can also see that as a non-deterministic epistemic action with two alternatives, where one is preferred over the other, and there is a natural generalization to general epistemic actions with preferences. (shrink)

This paper extends earlier work by its authors on formal aspects of the processes of contracting a theory to eliminate a proposition and revising a theory to introduce a proposition. In the course of the earlier work, Gardenfors developed general postulates of a more or less equational nature for such processes, whilst Alchourron and Makinson studied the particular case of contraction functions that are maximal, in the sense of yielding a maximal subset of the theory (or alternatively, of one of (...) its axiomatic bases), that fails to imply the proposition being eliminated. In the present paper, the authors study a broader class, including contraction functions that may be less than maximal. Specifically, they investigate "partial meet contraction functions", which are defined to yield the intersection of some nonempty family of maximal subsets of the theory that fail to imply the proposition being eliminated. Basic properties of these functions are established: it is shown in particular that they satisfy the Gardenfors postulates, and moreover that they are sufficiently general to provide a representation theorem for those postulates. Some special classes of partial meet contraction functions, notably those that are "relational" and "transitively relational", are studied in detail, and their connections with certain "supplementary postulates" of Gardenfors investigated, with a further representation theorem established. (shrink)

We show how belief revision can be treated systematically in the format of dynamicepistemic logic, when operators of conditional belief are added. The core engine consists of definable update rules for changing plausibility relations between worlds, which have been proposed independently in the dynamic-epistemic literature on preference change. Our analysis yields two new types of modal result. First, we obtain complete logics for concrete mechanisms of belief revision, based on compositional reduction axioms. Next, we show how various abstract postulates for (...) belief revision can be analyzed by standard modal frame correspondences for model-changing operations. (shrink)

In this paper we introduce Dynamic Epistemic Logic, which is alogic for reasoning about information change in a multi-agent system. Theinformation structures we use are based on non-well-founded sets, and canbe conceived as bisimulation classes of Kripke models. On these structures,we define a notion of information change that is inspired by UpdateSemantics (Veltman, 1996). We give a sound and complete axiomatization ofthe resulting logic, and we discuss applications to the puzzle of the dirtychildren, and to knowledge programs.

Tim French, Wiebe van der Hoek, Petar Iliev and Barteld Kooi. Succinctness of Epistemic Languages. In: T. Walsh (editor). Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI-11), pp. 881-886, AAAI Press, Menlo Park.

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)

In this paper we present a new modeling for belief revision that is what we term irrevocable. This modeling is of philosophical interest since it captures some features of suppositional reasoning, and of formal interest since it is closely connected with AGM, yet provides for iterated belief revision. The analysis is couched in terms of dynamic doxastic logic.

We present Arrow Update Logic, a theory of epistemic access elimination that can be used to reason about multi-agent belief change. While the belief-changing of Arrow Update Logic can be transformed into equivalent belief-changing from the popular Dynamic Epistemic Logic approach, we prove that arrow updates are sometimes exponentially more succinct than action models. Further, since many examples of belief change are naturally thought of from Arrow Update Logicrelativized” common knowledge familiar from the Dynamic Epistemic Logic literature.

Statements not only update our current knowledge, but also have other dynamic effects. In particular, suggestions or commands ?upgrade' our preferences by changing the current order among worlds. We present a complete logic of knowledge update plus preference upgrade that works with dynamic-epistemic-style reduction axioms. This system can model changing obligations, conflicting commands, or ?regret'. We then show how to derive reduction axioms from arbitrary definable relation changes. This style of analysis also has a product update version with preferences between (...) actions, as well as worlds. Some illustrations are presented involving defaults and obligations. We conclude that our dynamic framework is viable, while admitting a further extension to more numerical ?utility update'. (shrink)

In 1985 Alchourrón, Gärdenfors and Makinson presented their now classic theory of theory change . In 1988 Adam Grove, generalizing David Lewis's theory of counterfactuals, presented a model theory suitable for the AGM theory. Although AGM and Grove mentioned object languages, neither used them. But recently, Maarten de Rijke has shown how object languages can be brought into the picture. In the present paper we take de Rijke's idea further, addressing the question whether there is a particular doxastic or epistemic (...) logic implicit in AGM. (shrink)