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.
Type de document :
Communication dans un congrès
IJCAI 2013 - 23rd International Joint Conference on Artificial Intelligence, Aug 2013, Beijing, China. AAAI
https://hal.inria.fr/hal-01098744
Contributeur : Sophie Pinchinat
<>
Soumis le : lundi 29 décembre 2014 - 10:02:49
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Laura Bozzelli, Hans P. Van Ditmarsch, Sophie Pinchinat. The Complexity of One-Agent Refinement Modal Logic. IJCAI 2013 - 23rd International Joint Conference on Artificial Intelligence, Aug 2013, Beijing, China. AAAI. 〈hal-01098744〉
