A Recursive Shortcut for CEGAR: Application To The Modal Logic K Satisfiability Problem

Jean-Marie Lagniez, Daniel Le Berre, Tiago de Lima, Valentin MontmirailIJCAI 2017 · DOI

TL;DR

This paper introduces RECAR, a novel recursive extension to the Counter-Example-Guided Abstraction Refinement (CEGAR) technique, designed to tackle complex satisfiability problems. By strategically interleaving over- and under-approximations, RECAR significantly improves performance on unsatisfiable instances, outperforming standard CEGAR and state-of-the-art solvers on modal logic K satisfiability benchmarks.

What Problem Does This Paper Address?

Deciding the satisfiability of formulas in complex logical systems, like modal logic K, is computationally challenging (PSPACE-complete). Traditional approaches often translate these problems into propositional logic (SAT), but this can lead to exponentially larger formulas that are impractical to solve. CEGAR offers a more efficient way by using abstractions and iteratively refining them. However, standard CEGAR struggles with unsatisfiable instances, as it may require many refinement steps to prove unsatisfiability. This paper addresses this limitation by proposing a more robust CEGAR variant that can handle unsatisfiable cases more effectively.

Methods

The core contribution is the RECAR (Recursive Explore and Check Abstraction Refinement) approach. RECAR builds upon the standard CEGAR framework by introducing a recursive step that allows for the use of under-approximations.

Here's how it works:

  • CEGAR Basics: CEGAR uses an over-approximation of the original problem. If this abstraction is unsatisfiable, the original problem is also unsatisfiable (UNSAT shortcut). If it's satisfiable, the CEGAR process checks if the found model is valid for the original problem. If not, it refines the abstraction to exclude "spurious" models.
  • RECAR's Innovation: RECAR interleaves over- and under-approximations. When a strict under-approximation can be found, RECAR makes a recursive call to itself with this under-approximation. This recursive call acts as an additional UNSAT shortcut. The key idea is that proving unsatisfiability on a smaller, under-approximated problem can quickly lead to proving unsatisfiability for the original, larger problem.
  • Modal Logic K Application: The paper instantiates RECAR for modal logic K satisfiability. This involves defining specific translation functions from modal logic K formulas to propositional logic (CNF) and developing concrete over- and under-approximation strategies tailored for this domain.

Datasets

The paper evaluates RECAR on several benchmark sets for modal logic satisfiability:

  • Modalised random QBF (MQBF) formulae.
  • LWB basic modal logic benchmark formulae.
  • Randomly generated 3CNFKSP formulae.

The authors note that there isn't a standard benchmark specifically for modal logic K with multiple modalities, so they use existing, related benchmarks.

Key Insights and Ideas

  • The Power of Under-Approximation for Unsatisfiability: While over-approximations are good for finding satisfying models, under-approximations are crucial for efficiently proving unsatisfiability. RECAR leverages this by using recursive calls on under-approximations as a powerful UNSAT shortcut.
  • Recursive Abstraction is Key: The recursive nature of RECAR allows it to explore different levels of abstraction dynamically. This is more powerful than a single-level CEGAR approach, especially when dealing with problems that are difficult to satisfy.
  • Practicality for Modal Logic K: The paper demonstrates that RECAR, when applied to modal logic K, can significantly outperform existing state-of-the-art solvers, suggesting its broad applicability to complex logical reasoning tasks.
  • CEGAR's Weakness on Unsatisfiable Instances: The experimental results clearly show that standard CEGAR performs poorly on benchmarks that are unsatisfiable, highlighting the need for techniques like RECAR.

Key Results

  • RECAR vs. CEGAR: On most benchmarks, RECAR significantly outperforms the standard CEGAR approach. This is particularly evident for unsatisfiable benchmarks, where RECAR solves many more instances (1118/1367) compared to CEGAR (155/1367). For satisfiable benchmarks, RECAR also shows an advantage (1446 vs. 1053).
  • RECAR vs. State-of-the-Art: RECAR outperforms most other tested solvers, including Km2SAT, SAT, and Spartacus. While Km2SAT and SAT also employ techniques to handle unsatisfiable instances, RECAR's recursive approach proves more effective on the chosen benchmarks.
  • MoSaiC Solver: The implementation of RECAR within the MoSaiC solver shows competitive performance.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that for some benchmarks, solvers like Spartacus exhaust available memory while MoSaiC times out, indicating different resource utilization patterns and limits.
  • The translation from modal logic to propositional logic can still result in large formulas, even with RECAR.
  • Future Work:
    • Extending MoSaiC and the RECAR approach to other modal logics (e.g., KT, S4, S5, KD45) by adapting the translation functions.
  • Investigating RECAR's applicability to other decision problems beyond NP in the polynomial hierarchy.
  • Exploring whether existing CEGAR-related approaches for Quantified Boolean Formulas (QBF) can be integrated into the RECAR framework.

Summary updated

BibTeX
@inproceedings{lagniez2017recursive,
  author = {Jean-Marie Lagniez and Daniel Le Berre and Tiago de Lima and Valentin Montmirail},
  title = {{A Recursive Shortcut for CEGAR: Application To The Modal Logic K Satisfiability Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/94},
}
Figure