Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results



Belardinelli, Francesco and van der Hoek, Wiebe
(2015) Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results. PROCEEDINGS OF THE TWENTY-FOURTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI), 2015-J. pp. 2748-2754.

[img] Text
IJCAI15-389.pdf - Author Accepted Manuscript

Download (633kB)

Abstract

We introduce epistemic quantified boolean logic (EQBL), an extension of propositional epistemic logic with quantification over propositions. We show that EQBL can express relevant properties about agents' knowledge in multi-agent contexts, such as "agent a knows as much as agent b". We analyse the expressiveness of EQBL through a translation into monadic second-order logic, and provide completeness results w.r.t. various classes of Kripke frames. Finally, we prove that model checking EQBL is PSPACE-complete. Thus, the complexity of model checking EQBL is no harder than for (non-modal) quantified boolean logic.

Item Type: Article
Depositing User: Symplectic Admin
Date Deposited: 21 Aug 2015 10:54
Last Modified: 16 Dec 2022 05:22
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/2021200