College Publications logo   College Publications title  
View Basket
Homepage Contact page
Academia Brasileira de Filosofia
Cadernos de Lógica e Computação
Cadernos de Lógica e Filosofia
Cahiers de Logique et d'Epistemologie
Communication, Mind and Language
Cuadernos de lógica, Epistemología y Lenguaje
Encyclopaedia of Logic
Historia Logicae
IfColog series in Computational Logic
IfColog Lecture series
IfColog Proceedings
Journal of Applied Logics - IfCoLog Journal
Editorial Board
Scope of the Journal
Forthcoming papers
Logics for New-Generation AI
Logic and Law
Logic and Semiotics
Logic PhDs
Logic, Methodology and Philosophy of Science
The Logica Yearbook
Neural Computing and Artificial Intelligence
The SILFS series
Studies in Logic
Studies in Talmudic Logic
Texts in Logic and Reasoning
Texts in Mathematics
Digital Downloads
Information for authors
About us
Search for Books

Forthcoming papers


On the Computational Complexity of Model Checking for Dynamic Epistemic Logic with S5 Models

Ronald de Haan and Iris Pol

Dynamic epistemic logic (DEL) is a logical framework for representing
and reasoning about knowledge change for multiple agents. An important
computational task in this framework is the model checking problem, which
has been shown to be PSPACE-hard even for S5 models and two agents—in
the presence of other features, such as multi-pointed models. We answer open
questions in the literature about the complexity of this problem in more restricted
settings. We provide a detailed complexity analysis of the model checking
problem for DEL, where we consider various combinations of restrictions, such
as the number of agents, whether the models are single-pointed or multi-pointed,
and whether postconditions are allowed in the updates. In particular, we show
that the problem is already PSPACE-hard in (1) the case of one agent, multipointed
S5 models, and no postconditions, and (2) the case of two agents, only
single-pointed S5 models, and no postconditions. In addition, we study the
setting where only semi-private announcements are allowed as updates. We
show that for this case the problem is already PSPACE-hard when restricted
to two agents and three propositional variables. The results that we obtain in
this paper help outline the exact boundaries of the restricted settings for which the model checking problem for DEL is computationally tractable.

3 September 2020

© 2005–2022 College Publications / VFH webmaster