Efficient Representations for the Modal Logic S5
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1223-1228.
Abstract
We investigate efficient representations of subjective formulas in the modal logic of knowledge, S5, and more generally of sets of sets of propositional assignments. One motivation for this study is contingent planning, for which many approaches use operations on such formulas, and can clearly take advantage of efficient representations. We study the language S5-DNF introduced by Bienvenu et al., and a natural variant of it that uses Binary Decision Diagrams at the propositional level. We also introduce an alternative language, called Epistemic Splitting Diagrams, which provides more compact representations. We compare all three languages from the complexity-theoretic viewpoint of knowledge compilation and also through experiments. Our work sheds light on the pros and cons of each representation in both theory and practice.
@inproceedings{ijcai2016p177,
title = {Efficient Representations for the Modal Logic S5},
author = {Niveau, Alexandre and Zanuttini, Bruno},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {1223--1228},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/177},
}
TY - CPAPER TI - Efficient Representations for the Modal Logic S5 AU - Niveau, Alexandre AU - Zanuttini, Bruno T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 1223 EP - 1228 UR - https://ijcai.org/proceedings/2016/177 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
