The undecidability of arbitrary arrow update logic



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.

[img] 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