On evaluating decision procedures for modal logic

IJCAI 1997

TL;DR

This paper critically re-evaluates claims about the performance of modal logic decision procedures, specifically challenging the superiority of SAT-based methods like KSAT over tableaux-based systems like KRIS. The authors demonstrate that the benchmark generation method used in prior work produces overly simple formulas, masking the true complexity and leading to misleading conclusions about algorithm performance.

What Problem Does This Paper Address?

Automated reasoning for modal logics is a crucial area for knowledge representation and artificial intelligence. While various decision procedures exist (e.g., SAT-based, tableaux-based, translation to first-order logic), empirical evaluations are essential for understanding their practical performance. Giunchiglia and Sebastiani previously proposed an evaluation method and claimed that their SAT-based procedure, KSAT, significantly outperformed other methods, including tableaux-based KRIS, and exhibited an "easy-hard-easy" pattern on randomly generated modal formulas. This paper addresses the validity of these claims by scrutinizing the evaluation methodology and the quality of the generated benchmarks. The authors aim to provide a more accurate understanding of the comparative performance of these modal logic decision procedures.

Methods

The paper compares three main approaches to modal logic decision procedures:

  • KSAT: A SAT-based procedure adapted from propositional logic. It uses a preprocessing step to eliminate trivial tautologies and contradictions.
  • KTUS (or KRIS): A tableaux-based system that directly manipulates modal formulas.
  • Translation Approach (TA): Translates modal formulas into first-order logic, which are then handled by a standard first-order theorem prover (SPASS).

The authors' primary method is to re-evaluate the benchmark generation and testing methodology proposed by Giunchiglia and Sebastiani. They analyze the structure of the randomly generated modal CNF (Conjunctive Normal Form) formulas and their impact on the performance of KSAT and KRIS. They also introduce a modified version of KRIS, denoted KRIS*, which includes the preprocessing step found in KSAT, to isolate the effect of preprocessing versus the core algorithm.

Datasets

The paper evaluates decision procedures using randomly generated modal CNF (Conjunctive Normal Form) formulae. These formulae are generated using a method adapted from propositional logic benchmarks, with parameters including:

  • Number of propositional variables (N)
  • Number of modalities (M)
  • Number of modal subformulae per disjunction (K)
  • Number of modal subformulae per conjunction (L)
  • Modal degree (D)
  • Probability (P)

The authors specifically focus on parameter settings PSO (N=3, M=1, K=3, D=5) and PS1 (N=5, M=1, K=3, D=2) from Giunchiglia and Sebastiani's work. They highlight that these generated formulae often contain a significant amount of "logical garbage" (tautological and contradictory subformulae) that can be removed with preprocessing.

Key Insights and Ideas

  • Benchmark Quality is Crucial: The core insight is that the random modal CNF generator used by Giunchiglia and Sebastiani produces formulae that are often trivially satisfiable or unsatisfiable. This "easy" nature of the generated problems, particularly for larger L/N ratios, masks the true computational difficulty of modal logic reasoning.
  • Preprocessing Dominates Performance: The preprocessing step in KSAT, which removes redundant subformulae, has a dramatic impact on its performance. When this preprocessing is removed (KSATO), its performance degrades significantly, often by orders of magnitude, making it comparable to or worse than KRIS.
  • "Easy-Hard-Easy" Pattern is Artificial: The observed "easy-hard-easy" pattern for KSAT is largely an artifact of the benchmark generator and the preprocessing step. When preprocessing is removed or when more challenging formulae are used, this pattern is not as pronounced.
  • Tableaux vs. SAT is Not a Simple Dichotomy: The claim that SAT-based procedures are intrinsically more efficient than tableaux-based ones is questioned. The authors show that with preprocessing, KRIS* performs much better, suggesting that the comparison needs to account for such optimizations.
  • Challenging Formulae are Needed: The paper emphasizes the need for more carefully designed benchmarks that generate genuinely difficult instances to accurately compare decision procedures.

Key Results

  • KSAT's Superiority is Overstated: When the preprocessing step is removed from KSAT (resulting in KSATO), its performance is significantly worse, often by orders of magnitude, compared to the original KSAT.
  • KRIS* (KRIS with preprocessing) is Competitive: With preprocessing added, KRIS* shows much improved performance, narrowing the gap with KSAT. While KSAT still often performs better, the qualitative difference is reduced.
  • Trivially Unsatisfiable Formulae Dominate: For the tested parameter settings, almost all unsatisfiable formulae generated are "trivially unsatisfiable," meaning their unsatisfiability can be detected with minimal effort. This makes them poor test cases for complex reasoning.
  • The "Easy-Hard-Easy" Pattern is an Artifact: The peaking behavior observed in KSAT's performance is linked to the point where trivially unsatisfiable formulae become prevalent, and it is largely mitigated when preprocessing is absent or when more challenging formulae are considered.

Limitations and Future Work

  • Limitations of Current Benchmarks: The primary limitation identified is the quality of the randomly generated modal CNF formulae. They are too simple and contain too much redundant information, failing to generate challenging unsatisfiable instances.
  • Need for Better Benchmarks: The authors suggest that further investigations are required concerning the parameter settings and fundamental properties of modal KCNF formulae to create more suitable benchmarks.
  • Further Analysis of KRIS: While KRIS* is introduced, a more in-depth analysis of its performance across various settings, especially compared to KSAT on more challenging instances, would be beneficial.
  • Understanding the "Hard" Instances: The paper hints at the nature of "hard" instances for KSAT (where satisfiability in non-propositional contexts is essential) and suggests that the translation approach might handle these differently, warranting further comparative study.

Summary updated

BibTeX
@inproceedings{1997evaluating,
  title = {{On evaluating decision procedures for modal logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure