Logikk og AI

Ny tidsskriftsartikkel

Public announcement logic with distributed knowledge: expressivity, completeness and complexity.




While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics with distributed knowledge have so far received far less attention. In this paper we study extensions of public announcement logic ( PAL ) with distributed knowledge, in particular their expressivity, axiomatisations and complexity. PAL extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on PACD , the result of adding both common and distributed knowledge to PAL , which is more expressive than each of its component logics. We introduce an axiomatisation of PACD , which is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing with S5 knowledge, distributed knowledge, common knowledge and public announcements at the same time. We furthermore show that PACD is decidable, more precisely that it is \textscexptime -complete. This result also carries over to S5CD with common and distributed knowledge operators for all coalitions (and not only the grand coalition). Finally, we propose a notion of a trans-bisimulation to generalise certain results and give deeper insight into the proofs.

Thomas Ågotnes is professor at Department of Information Science and Media Studies, UiB.