A SAT-Based Approach for Solving the Modal Logic S5-Satisfiability Problem - Université Côte d'Azur Access content directly
Conference Papers Year : 2017

A SAT-Based Approach for Solving the Modal Logic S5-Satisfiability Problem

Thomas Caridroit
  • Function : Author
  • PersonId : 1052800
Tiago de Lima


We present a SAT-based approach for solving the modal logic S5-satisfiability problem. That problem being NP-complete, the translation into SAT is not a surprise. Our contribution is to greatly reduce the number of propositional variables and clauses required to encode the problem. We first present a syntactic property called diamond degree. We show that the size of an S5-model satisfying a formula φ can be bounded by its diamond degree. Such measure can thus be used as an upper bound for generating a SAT encoding for the S5-satisfiability of that formula. We also propose a lightweight caching system which allows us to further reduce the size of the propositional formula. We implemented a generic SAT-based approach within the modal logic S5 solver S52SAT. It allowed us to compare experimentally our new upper-bound against previously known one, i.e. the number of modalities of φ and to evaluate the effect of our caching technique. We also compared our solver against existing modal logic S5 solvers. The proposed approach outperforms previous ones on the benchmarks used. These promising results open interesting research directions for the practical resolution of others modal logics (e.g. K, KT, S4)
Fichier principal
Vignette du fichier
AAAI.pdf (1.45 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-02271408 , version 1 (26-08-2019)


  • HAL Id : hal-02271408 , version 1


Thomas Caridroit, Jean-Marie Lagniez, Daniel Le Berre, Tiago de Lima, Valentin Montmirail. A SAT-Based Approach for Solving the Modal Logic S5-Satisfiability Problem. Thirty-First AAAI Conference on Artificial Intelligence, Feb 2017, San Francisco, United States. ⟨hal-02271408⟩
149 View
122 Download


Gmail Mastodon Facebook X LinkedIn More