Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results

(2015) Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. pp. 2748-2754.

Text IJCAI15-389.pdf - Accepted Version 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:	31 Mar 2016 10:09
Last Modified:	31 Mar 2016 10:09
DOI:	http://ijcai.org/papers15/Papers/IJCAI15-389.pdf
URI:	http://livrepository.liverpool.ac.uk/id/eprint/2022485

Repository Staff Access