Almost APAL



van Ditmarsch, Hans, Liu, Mo, Kuijer, Louwe B ORCID: 0000-0001-6696-9023 and Sedlar, Igor
(2023) Almost APAL. JOURNAL OF LOGIC AND COMPUTATION, 33 (6). pp. 1350-1378.

[img] Text
1journalversion.pdf - Author Accepted Manuscript

Download (490kB) | Preview

Abstract

<jats:title>Abstract</jats:title><jats:p>Arbitrary public announcement logic (APAL) is a logic of change of knowledge with modalities representing quantification over announcements. We present two rather different versions of APAL wherein this quantification is restricted to formulas only containing a subset of all propositional variables: SAPAL and SCAPAL. Such restrictions are relevant in principle for the specification of multi-agent system dynamics. We also present another version of APAL, quantifying over all announcements implied by or implying a given formula: IPAL. We then determine the relative expressivity of all these logics and APAL. We also present complete axiomatizations of SAPAL and SCAPAL and show undecidability of satisfiability for all logics involved, by arguments nearly identical to those for APAL. We show that the IPAL quantifier, motivated by the satisfaction clause for substructural implication, yields a new substructural dynamic consequence relation.</jats:p>

Item Type: Article
Uncontrolled Keywords: APAL, quantification over announcements, substructural logic, expressivity
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 26 Nov 2021 08:44
Last Modified: 27 Nov 2023 09:52
DOI: 10.1093/logcom/exac012
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3143839