5 April 2005
4:00 - 5:30   Mehrnoosh Sadrzadeh
An Algebraic / Categorical Approach to the Logic of Information Flow
Joint work with Alexandru Baltag and Bob Coecke, Oxford University ComLab

Abstract

In an interactive multi-agent system, agents communicate with each other and this communication changes their information state. In order to reason about information updates in such settings, one has to take into account the dynamic as well as the epistemic aspect of communication. The traditional approaches only consider the epistemic aspect and dismiss the dynamic one. Recent development of Dynamic Epistemic Logic integrates both in a {\sf PDL} style logic with kripke semantics.
OUTLINE: I shall first show how this combinatorial setting can be generalized to an order theoretic structure that has a non-boolean resource-sensitive nature and considers communication actions as fundamental operations of an algebra rather than concrete constructions on a Kripke model. The algebra consists of an \em epistemic system \em $(M,Q,\{f_A\}_{A \in {\cal A}})$, which is a quantale-module pair $(M,Q)$ endowed with a family of ``appearance maps" for each agent $f_A = (f_A^M:M \to M, f_A^Q:Q \to Q)$. The right Galois adjoint to the appearance map gives rise to the ``box" modality of epistemic logic (expressing knowledge or belief of some agent).
I shall then briefly present a sound and complete Lambek - style sequent calculus based on the algebra that enables us to reason about communications and their effects in a semi-automatic way. Interesting examples will be presented including a cheating version of the muddy children puzzle and a security protocol!
Finally and most importantly, I shall show how moving to a sup-enriched categorical setting provides us a super elegant structure and allows each agent to have his own update schema.