The undecidability of arbitrary arrow update logic

van Ditmarsch, Hans, van der Hoek, Wiebe ORCID: 0000-0003-0721-0310 and Kuijer, Louwe B ORCID: 0000-0001-6696-9023 (2017) The undecidability of arbitrary arrow update logic THEORETICAL COMPUTER SCIENCE, 693. pp. 1-12. ISSN 0304-3975, 1879-2294

Text 1609.05686v1.pdf - Published version Download (182kB)

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 logics, Undecidability, Satisfiability
Depositing User:	Symplectic Admin
Date Deposited:	07 Nov 2016 08:24
Last Modified:	16 Jun 2026 04:49
DOI:	10.1016/j.tcs.2017.07.018
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3004386
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.