Undecidability for arbitrary public announcement logic
Tim French, Hans P. van Ditmarsch · UWA Profiles and Research Repository (University of Western Australia) · 2008
Arbitrary public announcement logic (AP AL) is an extension of multi-agent epistemic logic that allows agents' knowledge states to be updated by the public announcement of (possibly arbitrary) epistemic for- mulae. It has been shown to be more expressive than epistemic logic, and a sound and complete axiomatization has been given. Here we address the question of decidability. We present a proof that the satisfiability problem for arbitrary public announcement logic (AP AL) is co-RE complete, via a tiling argument.