Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 2748-2753.
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.
@inproceedings{ijcai2015p389,
title = {Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results},
author = {Belardinelli, Francesco and van der Hoek, Wiebe},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {2748--2753},
year = {2015},
month = {7},
note = {Special Track on Knowledge Representation and Reasoning},
url = {https://ijcai.org/proceedings/2015/389},
}
TY - CPAPER TI - Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results AU - Belardinelli, Francesco AU - van der Hoek, Wiebe T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 2748 EP - 2753 UR - https://ijcai.org/proceedings/2015/389 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
