On the Complexity of Dynamic Epistemic Logic

Guillaume Aucher 1 François Schwarzentruber 2
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
2 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.
Type de document :
Communication dans un congrès
TARK - Theoretical Aspects of Rationality and Knowledge - 2013, Jan 2013, Chennai, India. 2013
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00856468
Contributeur : Guillaume Aucher <>
Soumis le : dimanche 1 septembre 2013 - 01:13:02
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : jeudi 6 avril 2017 - 11:20:48

Fichier

TARK2013.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00856468, version 1

Citation

Guillaume Aucher, François Schwarzentruber. On the Complexity of Dynamic Epistemic Logic. TARK - Theoretical Aspects of Rationality and Knowledge - 2013, Jan 2013, Chennai, India. 2013. 〈hal-00856468〉

Partager

Métriques

Consultations de la notice

453

Téléchargements de fichiers

153