SAT-Based Explicit LTLf Satisfiability Checking

Jianwen Li, Kristin Y. Rozier, Geguang Pu, Yueling Zhang, Moshe Y. VardiAAAI 2019 · DOI

Introduction

Linear Temporal Logic (LTL) is a cornerstone of formal verification, traditionally used to describe infinite system behaviors. However, emerging fields like automated planning and business process modeling require reasoning over finite traces, leading to the development of $LTL_f$. The core challenge in $LTL_f$ is satisfiability checking: determining if a finite sequence of events exists that satisfies a given formula. Existing approaches often suffer from inefficiencies, either by unnecessarily treating finite traces as infinite "lassos" or by using explicit tableau-based methods that scale poorly with formula complexity.

Methodology: The CDLSC Framework

To address these limitations, researchers introduced CDLSC (Conflict-Driven $LTL_f$ Satisfiability Checking). This framework leverages the efficiency of modern propositional SAT solvers to explore the state space of an $LTL_f$ formula on-the-fly.

Algorithm 1: The CDLSC implementation logic, featuring the core satisfiability and invariant checking loops.

The "conflict-driven" nature of CDLSC is its primary innovation. Unlike traditional methods, it maintains a "conflict sequence"—sets of states proven unreachable to a satisfying conclusion within a specific number of steps. When the SAT solver encounters an unsatisfiable state, it identifies an Unsatisfiable Core (UC)—the minimal subset of the formula causing the failure. By blocking all states sharing this UC, CDLSC prunes vast sections of the search space, effectively "learning" from failure to avoid redundant computations.

Experimental Evaluation

The CDLSC tool was evaluated against a comprehensive suite of 9,142 formulas, including standard LTL benchmarks adapted for finite traces and $LTL_f$-specific patterns. The evaluation compared CDLSC with state-of-the-art solvers such as Aalta-finite, ltl2sat, and the IC3+K-LIVE backend of nuXmv.

Performance comparison showing CDLSC's significant speed advantage over competing solvers across a large benchmark suite.

The results demonstrate a decisive performance leap. CDLSC achieved an average four-fold speedup over the previous best-performing tool (IC3+K-LIVE). On particularly challenging "Practical Conjunction" benchmarks, CDLSC completed the task in 115 seconds, whereas the next best dedicated $LTL_f$ tool, Aalta-infinite, required over 4,400 seconds.

Conclusion

CDLSC proves that dedicated SAT-based frameworks are superior for finite-trace temporal logic. By avoiding the "lasso tax" of infinite-trace reductions and employing intelligent pruning via unsatisfiable cores, it sets a new speed record for $LTL_f$ satisfiability. Future work may involve exploring symbolic state representations for even larger systems and further tuning heuristics for specific AI domains like robotics.

Summary updated

BibTeX
@inproceedings{li2019sat,
  author = {Jianwen Li and Kristin Y. Rozier and Geguang Pu and Yueling Zhang and Moshe Y. Vardi},
  title = {{SAT-Based Explicit LTLf Satisfiability Checking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012946},
}
Figure