Parameterized Complexity of Dynamic Belief Updates

Thomas Bolander, Arnaud Lequen*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review


Dynamic Belief Update (DBU) is a model checking problem in Dynamic Epistemic Logic (DEL) concerning the effect of applying a number of epistemic actions on an initial epistemic model. It can also be considered as a plan verification problem in epistemic planning. The problem is known to be PSPACE-hard. To better understand the source of complexity of the problem, previous research has investigated the complexity of 128 parameterized versions of the problem with parameters such as number of agents and size of actions. The complexity of many parameter combinations has been determined, but previous research left a few combinations as open problems. In this paper, we solve most of the remaining open problems by proving all of them to be fixed-parameter intractable. Only two parameter combinations are still left as open problem for future research.
Original languageEnglish
Title of host publicationDynamic Logic. New Trends and Applications
Publication date2020
ISBN (Print)978-3-030-65839-7
Publication statusPublished - 2020
Event3rd International Workshop on Dynamic Logic - Virtual event, Prague, Czech Republic
Duration: 9 Oct 202010 Oct 2020


Conference3rd International Workshop on Dynamic Logic
LocationVirtual event
Country/TerritoryCzech Republic
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


  • Parameterized complexity
  • Model checking
  • Dynamic Epistemic Logic
  • Plan verification


Dive into the research topics of 'Parameterized Complexity of Dynamic Belief Updates'. Together they form a unique fingerprint.

Cite this