On the Complexity of Dynamic Epistemic Logic - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

On the Complexity of Dynamic Epistemic Logic

Résumé

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.
Fichier principal
Vignette du fichier
TARK2013.pdf (358.98 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00856468 , version 1 (01-09-2013)

Identifiants

  • HAL Id : hal-00856468 , version 1

Citer

Guillaume Aucher, François Schwarzentruber. On the Complexity of Dynamic Epistemic Logic. TARK - Theoretical Aspects of Rationality and Knowledge - 2013, Jan 2013, Chennai, India. ⟨hal-00856468⟩
388 Consultations
115 Téléchargements

Partager

Gmail Facebook X LinkedIn More