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.
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 |