Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results
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.
Cite
Text
Belardinelli and van der Hoek. "Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Belardinelli and van der Hoek. "Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/belardinelli2015ijcai-epistemic/)BibTeX
@inproceedings{belardinelli2015ijcai-epistemic,
title = {{Epistemic Quantified Boolean Logic: Expressiveness and Completeness Results}},
author = {Belardinelli, Francesco and van der Hoek, Wiebe},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {2748-2754},
url = {https://mlanthology.org/ijcai/2015/belardinelli2015ijcai-epistemic/}
}