A Tree-Shaped Tableau for Checking the Satisfiability of Signal Temporal Logic with Bounded Temporal Operators

Beatrice Melani, Ezio Bartocci, Michele Chiari

Introduction

Cyber-Physical Systems (CPS), ranging from autonomous vehicles to aerospace components, rely on rigorous specifications to ensure safety and performance. Signal Temporal Logic (STL) is a widely adopted formalism for expressing these requirements, allowing engineers to define complex constraints over continuous-valued signals over time. However, as system complexity grows, ensuring that a set of requirements is logically consistent—a property known as satisfiability—becomes a significant computational challenge.

Traditional methods for checking STL satisfiability typically involve translating the logic into Satisfiability Modulo Theories (SMT) problems. While robust, these SMT-based approaches often suffer from "state-space explosion." When requirements span long time horizons, the solver must instantiate variables for every discrete time step, leading to memory exhaustion or prohibitive computation times.

The Tree-Shaped Tableau Approach

To address these limitations, this research introduces a novel one-pass, tree-shaped tableau method specifically designed for discrete-time STL with bounded temporal operators. Unlike SMT solvers that attempt to solve the entire timeline globally, the tableau method constructs a search tree of possibilities step-by-step to find a valid signal.

The JUMP Rule: Overcoming Temporal Redundancy

The core innovation of this approach is the JUMP Rule. The researchers observed that in many CPS requirements, constraints remain constant over significant intervals. Traditional solvers increment time linearly ($t \to t+1$), redundantly re-evaluating the same logic at every tick. The JUMP rule identifies the next critical time point where a constraint's state might actually change and "jumps" the logical evaluation forward to that point. This effectively treats time as a sequence of meaningful events rather than a dense grid of identical clock ticks, drastically reducing the number of states the solver must explore.

Hybrid Optimization Techniques

The tableau method is further enhanced by several optimization strategies that combine structural search with numerical precision:

  • Local SMT Integration: Instead of using an SMT solver for the entire problem, the tool utilizes the Z3 solver to handle small, localized checks of linear constraints (e.g., $x > 5$) within individual tree nodes.
  • Memoization: To prevent redundant computation, the algorithm stores results from previously explored branches, allowing it to prune the search space when encountering familiar logical states.
  • Early Consistency Checks: The tool identifies obvious contradictions early in the branch expansion process, preventing the exploration of doomed paths.
  • Heuristic Operator Prioritization: By checking simpler requirements first, the algorithm can often identify unsatisfiability more quickly.

Experimental Evaluation

The authors evaluated their tool against three diverse benchmark suites to test its robustness and scalability:

  1. Standard STL Benchmarks: Classic problems from literature including automotive (Car), Thermostat, Water Tank, Railroad, and Battery models.
  2. Industrial Aerospace Requirements: A real-world set of 31 software functional requirements provided by an industrial partner.
  3. MLTL and Randomized Formulas: A suite of Mission-Time Linear Temporal Logic (MLTL) requirements from NASA and Boeing projects, alongside 8,000 randomly generated formulas.

Performance Results

The results demonstrate a clear advantage for the tableau approach in most scenarios:

  • Benchmark Dominance: The tableau outperformed traditional SMT encodings in 9 out of 10 non-trivial STL benchmarks.
  • Scalability: In a satellite system (CPS) benchmark with a massive time horizon of 13,799 steps, the SMT solver timed out at 120 seconds, while the tableau reached a solution in just 1.9 seconds.
  • Robustness: On randomly generated formulas—which are often less structured than human-written ones—the tableau drastically outperformed state-of-the-art First-Order Logic (FOL) encodings.

The only notable exception was the "Railroad" benchmark. Due to its highly nested and contradictory nature, the tableau was forced to explore nearly every possible branch, hitting a worst-case scenario for the search tree.

Conclusion and Future Work

The tree-shaped tableau method represents a significant advancement in the verification of CPS requirements. By leveraging the JUMP rule to bypass temporal redundancy and combining structural search with local SMT solving, the tool provides a scalable solution for long-horizon satisfiability checking in discrete-time systems.

Future work will focus on extending this framework toward Control Synthesis, where the tool not only checks for consistency but automatically generates the control code required to satisfy the specifications. Additionally, the authors plan to implement automatic example generation to provide engineers with visual traces of satisfying signals for consistent requirement sets.

Summary updated

BibTeX
@article{melani2025tree,
  author = {Beatrice Melani and Ezio Bartocci and Michele Chiari},
  title = {{A Tree-Shaped Tableau for Checking the Satisfiability of Signal Temporal Logic with Bounded Temporal Operators}},
  journal = {ACM Trans. Embed. Comput. Syst.},
  year = {2025},
  doi = {10.1145/3759917},
}
Figure