Logics of communication and change (Q859825)

The paper under review studies dynamic epistemic logics which allow for compositional analysis of the epistemic effects of informational events. Technically this means that the logics under consideration can be characterized by so-called reduction axioms. Such systems have simple completeness proofs since for every formula with announcement operators there is an equivalent formula without announcement operators. In the first part of the paper the notion of relativized common knowledge is introduced and completeness of a corresponding system EL-RC is shown by a canonical model construction. Adding a new modal operator for public announcements and corresponding reduction axioms yields the system PAL-RC, which is equivalent to EL-RC. However, PAL-RC is more expressive than PAL-C (which is PAL-RC where relativized common knowledge is replaced by the usual common knowledge operator). This is shown using a new variant of Ehrenfeucht games. In the second part a much richer logic, called logic of communication and change (LCC), is introduced. The static base of this logic is PDL, interpreted epistemically. This framework can also deal with factual change, making use of a notion of model update based on substitutions that change the values of some propositional letters. The authors illustrate the power of LCC by analyzing complex information scenarios like sending successive emails with both `cc' and `bcc' lines. Still, LCC can be reduced to PDL. The proof uses the idea behind Kleene's Theorem for regular languages and finite automata.