Skip to Main content Skip to Navigation

On the Complexity of Dynamic Epistemic Logic (Extended Version)

Guillaume Aucher 1 François Schwarzentruber 1 
1 DISTRIBCOM - Distributed and Iterative Algorithms for the Management of Telecommunications Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Although Dynamic Epistemic Logic (DEL) is an influential logical framework for representing and reasoning about information change, little is known about the computational complexity of its associated decision problems. In fact, we only know that for public announcement logic, a fragment of DEL, the satisfiability problem and the model-checking problem are respectively PSPACE-complete and in P. We contribute to fill this gap by proving that for the DEL language with event models, the model-checking problem is, surprisingly, PSPACE-complete. Also, we prove that the satisfiability problem is NEXPTIME-complete. In doing so, we provide a sound and complete tableau method deciding the satisfiability problem.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Guillaume Aucher Connect in order to contact the contributor
Submitted on : Friday, November 30, 2012 - 10:23:27 PM
Last modification on : Thursday, June 2, 2022 - 11:16:06 AM
Long-term archiving on: : Friday, March 1, 2013 - 3:58:37 AM


Files produced by the author(s)


  • HAL Id : hal-00759544, version 1


Guillaume Aucher, François Schwarzentruber. On the Complexity of Dynamic Epistemic Logic (Extended Version). [Research Report] RR-8164, INRIA. 2012. ⟨hal-00759544⟩



Record views


Files downloads