Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951976 | Theoretical Computer Science | 2017 | 12 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hans van Ditmarsch, Wiebe van der Hoek, Louwe B. Kuijer,