Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results

Belardinelli, Francesco and van der Hoek, Wiebe ORCID: 0000-0003-0721-0310 (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. ISSN 1045-0823

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 Jun 2026 06:02
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2021200
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.