Conference paper · Book chapter
Parameterized Complexity of Dynamic Belief Updates
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.
| Language: | English |
|---|---|
| Publisher: | Springer |
| Year: | 2020 |
| Pages: | 87-102 |
| Proceedings: | 3<sup>rd</sup> International Workshop on Dynamic Logic |
| Series: | Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| ISBN: | 3030658392 , 3030658406 , 9783030658397 and 9783030658403 |
| ISSN: | 03029743 |
| Types: | Conference paper and Book chapter |
| DOI: | 10.1007/978-3-030-65840-3_6 |
| ORCIDs: | Bolander, Thomas |
