The Undecidability of Arbitrary Arrow Update Logic

Autor:	van Ditmarsch, Hans, van der Hoek, Wiebe, Kuijer, Louwe B.
Rok vydání:	2016
Předmět:	Computer Science - Logic in Computer Science
Druh dokumentu:	Working Paper
Popis:	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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1609.05686 Zobrazit plný text záznamu View this record from Arxiv