Automata with Generalized Rabin Pairs for Probabilistic Model Checking and LTL Synthesis

Krishnendu Chatterjee, Andreas Gaiser, Jan Kretínský

Abstract

This paper introduces a more efficient methodology for verifying probabilistic systems and synthesizing controllers through the use of Deterministic Generalized Rabin Automata (DGRW). By bypassing the traditional, state-heavy Safra’s construction and operating directly on generalized Rabin acceptance conditions, the authors achieve state-space reductions and computational speedups of several orders of magnitude. The approach is validated through integration with the PRISM model checker, demonstrating its effectiveness on complex benchmarks.

Introduction

In formal verification, the goal is often to determine if a system, such as a communication protocol, satisfies a specification defined in Linear Temporal Logic (LTL). For probabilistic systems like Markov Decision Processes (MDPs) and for game-based synthesis, this necessitates the translation of LTL formulas into deterministic automata.

Historically, the standard approach has been the translation of LTL to Deterministic Rabin Automata (DRW) via Safra’s construction. However, Safra’s algorithm is notoriously complex and prone to generating "explosively" large automata. While modern "Safraless" techniques offer improvements, they frequently revert to standard Rabin formats for tool compatibility, a step that often negates previous gains by causing a massive blow-up in the state space.

Methods: Deterministic Generalized Rabin Automata

The authors propose a direct approach using Deterministic Generalized Rabin Automata (DGRW), effectively removing the need for intermediate conversions that inflate state counts.

The Acceptance Condition

A standard Rabin pair $(F, I)$ requires that states in set $F$ are visited finitely often, while states in set $I$ are visited infinitely often. In contrast, a Generalized Rabin pair allows for a conjunction of multiple Büchi conditions (infinitely often) paired with a single co-Büchi condition (finitely often).

Figure 1: A Deterministic Generalized Rabin Automaton (DGRW) for the LTL formula $Fa \lor Gb$.

Direct Algorithms and Avoiding Degeneralization

The core innovation lies in algorithms that perform probabilistic model checking and game solving directly on DGRW conditions. By avoiding the "degeneralization" step—which typically multiplies the state space by a Degeneralization Index ($|B|$)—the researchers maintain structural efficiency. In complex scenarios, this index can grow doubly exponentially; the DGRW approach bypasses this bottleneck entirely.

Key Insights: Structural Efficiency

The researchers identified that intermediate "Safraless" representations are often more efficient to use directly than the standard Rabin automata they are usually converted into. For the $(F, G)$ fragment of LTL (formulas involving "Eventually" and "Globally"), the DGRW representation provides the compactness of a Muller automaton while remaining algorithmically tractable.

Figure 2: Illustration of the state-space expansion (right) compared to the original automaton (left) when accounting for the degeneralization index.

Furthermore, DGRW handles conjunctions—common in real-world fairness constraints—natively within the acceptance condition. Standard Rabin automata struggle with these, leading to the aforementioned state-space explosions.

Evaluation and Results

The approach was evaluated using the Pnueli-Zuck Randomized Mutual Exclusion Protocol, synthetic game families, and integration into the PRISM model checker.

The experimental results demonstrated dramatic improvements:

  • State Space Reduction: For a benchmark with three strong fairness constraints, the standard ltl2dstar tool produced over one million states, whereas the DGRW approach required only 64 states.
  • Speedup: Probabilistic model checking benchmarks showed the new method to be 10 to 100 times faster than the original PRISM implementation.
  • Synthesis Performance: In LTL games, the DGRW method solved problems in seconds that previously caused timeouts or memory crashes.

Limitations and Future Work

Currently, the research focuses on the $(F, G)$ fragment of LTL, which excludes "Until" ($U$) and "Next" ($X$) operators. Future work aims to extend this generalized approach to full LTL and explore symbolic computation and acceleration techniques, such as Long’s acceleration, to further optimize game-solving algorithms.

Summary updated

BibTeX
@inproceedings{chatterjee2013automata,
  author = {Krishnendu Chatterjee and Andreas Gaiser and Jan Kretínský},
  title = {{Automata with Generalized Rabin Pairs for Probabilistic Model Checking and LTL Synthesis}},
  booktitle = {CAV},
  year = {2013},
  doi = {10.1007/978-3-642-39799-8\_37},
}
Figure