The Complexity of One-Agent Refinement Modal Logic

Laura Bozzelli 1 Hans Van Ditmarch 2 Sophie Pinchinat 3
3 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 ( \sffamily RML ), a known extension of basic modal logic ( \sffamily ML ) obtained by adding refinement quantifiers on structures. It is known that \sffamily RML has the same expressiveness as \sffamily ML , but the translation of \sffamily RML into \sffamily ML is of non-elementary complexity, and \sffamily RML is at least doubly exponentially more succinct than \sffamily ML . In this paper, we show that \sffamily RML -satisfiability is ‘only’ singly exponentially harder than \sffamily ML -satisfiability, the latter being a well-known PSPACE-complete problem. More precisely, we establish that \sffamily RML -satisfiability is complete for the complexity class AEXP \sffamily pol , i.e., the class of problems solvable by alternating Turing machines running in single exponential time but only with a polynomial number of alternations (note that NEXPTIME⊆ AEXP \sffamily pol ⊆ EXPSPACE).
Type de document :
Communication dans un congrès
JELIA 2012 - 13th European Conference on Logics in Artificial Intelligence, Sep 2012, Toulouse, France. Springer, Logics in Artificial Intelligence, 7519, pp.120-133, LNCS. 〈https://www.irit.fr/jelia2012/〉. 〈10.1007/978-3-642-33353-8_10〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01098749
Contributeur : Sophie Pinchinat <>
Soumis le : lundi 29 décembre 2014 - 10:30:21
Dernière modification le : mercredi 16 mai 2018 - 11:23:05

Lien texte intégral

Identifiants

Citation

Laura Bozzelli, Hans Van Ditmarch, Sophie Pinchinat. The Complexity of One-Agent Refinement Modal Logic. JELIA 2012 - 13th European Conference on Logics in Artificial Intelligence, Sep 2012, Toulouse, France. Springer, Logics in Artificial Intelligence, 7519, pp.120-133, LNCS. 〈https://www.irit.fr/jelia2012/〉. 〈10.1007/978-3-642-33353-8_10〉. 〈hal-01098749〉

Partager

Métriques

Consultations de la notice

215