van Ditmarsch, Hans, van der Hoek, Wiebe and Kuijer, Louwe B
(2017)
The undecidability of arbitrary arrow update logic.
THEORETICAL COMPUTER SCIENCE, 693.
pp. 1-12.
Text
1609.05686v1.pdf - Published version Download (182kB) |
Abstract
Arbitrary Arrow Update Logic is a dynamic modal logic that uses an arbitrary arrow update modality to quantify over all arrow updates. Some properties of this logic have already been established, but until now it remained an open question whether the logic's satisfiability problem is decidable. Here, we show that the satisfiability problem of Arbitrary Arrow Update Logic is co-RE hard, and therefore undecidable, by a reduction of the tiling problem.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Modal logic, Dynamic epistemic logic, Update logics, Undecidability, Satisfiability |
Depositing User: | Symplectic Admin |
Date Deposited: | 07 Nov 2016 08:24 |
Last Modified: | 19 Jan 2023 07:26 |
DOI: | 10.1016/j.tcs.2017.07.018 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3004386 |