The Undecidability of Arbitrary Arrow Update Logic

2016/09/19 by Hans van Ditmarsch, van Ditmarsch, Hans, Wiebe van der Hoek +3 · 1 citation
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Multi-Agent Systems and Negotiation #cs.LO

paper · pdf · doi:10.48550/arxiv.1609.05686

arxiv created 2016/09/19 · openalex publication_date 2016/09/19 · arxiv updated 2016/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Arbitrary Arrow Update Logic with Common Knowledge is neither RE nor co-RE

Related

• A Simplest Undecidable Modal Logic
• Undecidability of a Very Simple Modal Logic with Binding
• Two variable fragment of Term Modal Logic
• Undecidability of Linear Logics without Weakening
• A Decidable Bundled Fragment of First-Order Modal Logic Without Finite Model Property