The Complexity of One-Agent Refinement Modal Logic
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2977-2980.
Abstract
We investigate the complexity of satisfiability for one-agent refinement modal logic (RML), an extension of basic modal logic (ML) obtained by adding refinement quantifiers on structures. RML is known to have the same expressiveness as ML, but the translation of RML into ML is of non-elementary complexity, and RML is at least doubly exponentially more succinct than ML. In this paper we show that RML-satisfiability is 'only' singly exponentially harder than ML-satisfiability, the latter being a well-known PSPACE-complete problem.
@inproceedings{ijcai2013p440,
title = {The Complexity of One-Agent Refinement Modal Logic},
author = {Bozzelli, Laura and van Ditmarsch, Hans and Pinchinat, Sophie},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {2977--2980},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/440},
}
TY - CPAPER TI - The Complexity of One-Agent Refinement Modal Logic AU - Bozzelli, Laura AU - van Ditmarsch, Hans AU - Pinchinat, Sophie T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 2977 EP - 2980 UR - https://ijcai.org/proceedings/2013/440 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
