Leviathan: A New LTL Satisfiability Checking Tool Based on a One-Pass Tree-Shaped Tableau

Matteo Bertello, Nicola Gigante, Angelo Montanari, Mark ReynoldsIJCAI 2016

Abstract

Linear Temporal Logic (LTL) is a fundamental formalism for specifying the behavior of reactive systems. Checking the satisfiability of LTL formulas is a critical step in the verification process to ensure that specifications are not inherently contradictory. This paper introduces Leviathan, a high-performance LTL satisfiability checker based on a simplified "one-pass" tree-shaped tableau algorithm. By leveraging modern implementation techniques such as bitset optimizations and depth-first search, Leviathan achieves performance comparable to, and often exceeding, state-of-the-art tools based on more complex automata-theoretic or resolution-based approaches.

Introduction

Linear Temporal Logic (LTL) serves as the industry standard for describing temporal properties in model checking and synthesis. Before proceeding with expensive verification tasks, it is essential to determine if an LTL formula is satisfiable. However, LTL satisfiability is PSPACE-complete, presenting significant computational challenges.

Existing state-of-the-art solvers often rely on complex translations to Büchi automata or temporal resolution. While effective, these methods can be difficult to implement and optimize. Leviathan revisits the tableau-based approach, specifically a "one-pass" tree-shaped tableau, demonstrating that algorithmic simplicity combined with low-level optimization can yield a highly competitive tool.

Methodology: One-Pass Tree-Shaped Tableau

The core of Leviathan is its one-pass tree-shaped tableau algorithm. Unlike traditional "two-pass" tableau methods that first construct a large graph and then prune it, Leviathan builds a tree and determines the success or failure of branches on the fly.

Example of a tree-shaped tableau for an LTL formula.

Key Rules and Optimizations

To handle the infinite nature of time in LTL, Leviathan employs two critical rules:

  • LOOP Rule: This rule identifies when a branch has entered a repeating cycle that satisfies all required "eventualities" (formulas of the form $\Diamond p$ or $q \mathcal{U} p$). If such a cycle is found, the formula is declared satisfiable.
  • PRUNE Rule: Conversely, the PRUNE rule identifies "bad" infinite cycles where an eventuality is promised but never fulfilled. The authors refined this into a "three-node" pruning strategy, requiring three repetitions of a label before abandoning a branch to avoid premature termination.

Performance is further enhanced through Bitset Optimization. LTL subformulas are mapped to specific bits, allowing logical operations and contradiction checks (e.g., $p \land \neg p$) to be executed via fast CPU bitwise instructions. The search itself is conducted using a stack-based Depth-First Search (DFS), which maintains a linear memory footprint relative to the search depth.

Experimental Evaluation

Leviathan was evaluated on the StarExec platform using a comprehensive library of 3,723 LTL formulas. These include real-world-inspired benchmarks from the Anzu and Forobots synthesis projects, as well as challenging synthetic sets like the Rozier and Schuppan counters and the Alaska dataset.

Performance Results

Leviathan was compared against leading tools including Aalta (automata-based), LS4 (resolution-based), and NuSMV (symbolic model checker).

Comparison of Leviathan against other LTL solvers across various benchmark datasets.

The results, visualized in the benchmark comparison, highlight several key findings:

  • Speed: Leviathan achieved the lowest running times on the anzu, forobots, and non-counter rozier datasets.
  • Memory Efficiency: The tool demonstrated superior memory management, particularly on the schuppan and rozier-counter datasets, where competitors often exhausted available memory.
  • Tableau Comparison: Leviathan consistently outperformed PLTL, another tableau-based tool, validating the efficiency of the one-pass tree approach over graph-based methods.

While Leviathan performed exceptionally well on most sets, it encountered difficulties with the Alaska dataset, resulting in timeouts. However, even during these timeouts, its memory usage remained notably low.

Conclusion and Future Work

Leviathan proves that a well-optimized, simple tableau algorithm can be a powerful alternative to complex LTL satisfiability solvers. Its tree-based structure not only ensures memory efficiency but also makes it an ideal candidate for parallelization.

Future development will focus on incorporating search heuristics to prioritize promising branches, integrating modern SAT solvers to handle propositional logic more efficiently, and investigating specialized rules to improve performance on structurally complex datasets like Alaska.

This paper is based on the IJCAI-16 presentation by the authors of Leviathan.

Summary updated

BibTeX
@inproceedings{bertello2016leviathan,
  author = {Matteo Bertello and Nicola Gigante and Angelo Montanari and Mark Reynolds},
  title = {{Leviathan: A New LTL Satisfiability Checking Tool Based on a One-Pass Tree-Shaped Tableau}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure