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

Abstract

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
PublisherSpringer
Publication date2020
Pages87-102
ISBN (Print)978-3-030-65839-7
DOIs
Publication statusPublished - 2020
Event3rd International Workshop on Dynamic Logic - Virtual event, Prague, Czech Republic
Duration: 9 Oct 202010 Oct 2020

Conference

Conference3rd International Workshop on Dynamic Logic
LocationVirtual event
CountryCzech Republic
CityPrague
Period09/10/202010/10/2020
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12569
ISSN0302-9743

Keywords

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

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

Cite this