The Complexity of One-Agent Refinement Modal Logic

Laura Bozzelli 1 Hans P. Van Ditmarsch 2, 3, 4 Sophie Pinchinat 5
1 UPM - Universidad Politécnica de Madrid
2 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 Universidad de Sevilla
4 IMSc - Institute of Mathematical Sciences [India]
5 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
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
Liste complète des métadonnées
https://hal.inria.fr/hal-01098744
Contributeur : Sophie Pinchinat <>
Soumis le : lundi 29 décembre 2014 - 10:02:49
Dernière modification le : vendredi 16 novembre 2018 - 01:23:48

Identifiants

  • HAL Id : hal-01098744, version 1

Collections

INRIA | IRISA | IRISA-D4 | UR1-UFR-ISTIC | UNIV-LORRAINE | LORIA | UNIV-RENNES

Citation

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

184

Contact


archive-ouverte@inria.fr