The undecidability of arbitrary arrow update logic

van Ditmarsch, H, van der Hoek, W and Kuijer, L ORCID: 0000-0001-6696-9023 (2017) The undecidability of arbitrary arrow update logic. Theoretical Computer Science, 693. pp. 1-12.

Text AAUL_Undecidability_Revision.pdf - Author Accepted Manuscript Download (304kB)

Abstract

Arbitrary Arrow Update Logic is a dynamic modal logic with a modality to quantify over 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 by a reduction of the tiling problem that the satisfiability problem of Arbitrary Arrow Update Logic is co-RE hard, and therefore undecidable.

Item Type:	Article
Uncontrolled Keywords:	Modal logic, dynamic epistemic logic, update logic, undecidability, satisfiability
Depositing User:	Symplectic Admin
Date Deposited:	11 Aug 2017 10:07
Last Modified:	19 Jan 2023 06:58
DOI:	10.1016/j.tcs.2017.07.018
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3008920