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



Kuijer, Louwe B ORCID: 0000-0001-6696-9023
(2017) Arbitrary Arrow Update Logic with Common Knowledge is neither RE nor co-RE. In: Sixteenth conference on Theoretical Aspects of Rationality and Knowledge (TARK 2017).

[img] Text
AAULC_nonaxiomatizability_rev_v1.pdf - Author Accepted Manuscript

Download (167kB)

Abstract

Arbitrary Arrow Update Logic with Common Knowledge (AAULC) is a dynamic epistemic logic with (i) an arrow update operator, which represents a particular type of information change and (ii) an arbitrary arrow update operator, which quantifies over arrow updates. By encoding the execution of a Turing machine in AAULC, we show that neither the valid formulas nor the satisfiable formulas of AAULC are recursively enumerable. In particular, it follows that AAULC does not have a recursive axiomatization.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 12 Jun 2017 12:53
Last Modified: 04 Mar 2024 09:17
DOI: 10.4204/eptcs.251.27
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3007926