Logics of Communication and Change
Johan van Benthem, Jan van Eijck, Barteld Kooi

Abstract:
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.

Key words: epistemic logic, update, dynamic logic, common knowledge, reduction
axioms, product update, nite automata, Kleene's Theorem