💻 computer science

Complete Supermartingale Certificates for $\omega$ -Regular Properties

This paper introduces a general methodology that decomposes $\omega$ -regular properties into almost-sure termination obligations, enabling the construction of the first sound and complete (or $\varepsilon$ -complete) supermartingale certificates for verifying almost-sure and quantitative $\omega$ -regular properties on time-homogeneous Markov chains with countably infinite state spaces.

Original authors: Alessandro Abate, Mirco Giacobbe, Sergey Ichtchenko, Diptarko Roy

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessandro Abate, Mirco Giacobbe, Sergey Ichtchenko, Diptarko Roy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are managing a very complex, unpredictable casino game. The game involves a gambler with a fluctuating bankroll, and the rules change depending on whether the gambler is in debt or not. You want to prove a specific promise about the game: "Will the gambler eventually run out of money and stay broke forever, or will they keep bouncing back?"

In the world of computer science and mathematics, this kind of "forever" behavior is called an $\omega$ -regular property. It's a fancy way of asking questions about what happens over an infinite amount of time.

This paper introduces a new, powerful toolkit to answer these questions with absolute certainty (or near-certainty) for systems that are too complex to simulate on a computer. Here is how they did it, using simple analogies:

1. The Problem: The "Infinite" Puzzle

Traditionally, to prove things about these systems, mathematicians use "Supermartingale Certificates." Think of these as scorecards.

If you have a scorecard that shows the gambler's wealth is always trending downward on average, you can prove they will eventually go broke.
However, proving complex "forever" rules (like "they must visit the 'Debt' zone infinitely often, but the 'Rich' zone only finitely often") was like trying to solve a giant jigsaw puzzle with missing pieces. Previous methods were incomplete: they could prove the game was safe if the scorecard was perfect, but they couldn't prove the game was safe even if the scorecard was slightly imperfect, even if the game was actually safe.

2. The Solution: Breaking the Puzzle into Smaller Pieces

The authors' big breakthrough is a method called Absorbing-Region Decomposition.

Imagine the casino floor is a giant map. The authors realized you don't need to prove the whole map is safe at once. Instead, you can break the map into three manageable zones:

Zone A: The "Safe Zone" (The Invariant): This is a region of the map where, if you stay inside, the game behaves nicely. It's like a "safe room" in a video game.
Zone B: The "One-Way Trap" (The Absorbing Region): These are specific areas (like the "Debt" zone) that, once you enter, you can't easily escape back to the "Safe Zone." It's like a slide that only goes down.
Zone C: The "Exit Door": The path out of the Safe Zone.

The authors proved a magical rule: To prove the whole game works, you only need to prove three simple things:

Safety: If you are in the "Safe Zone," you are likely to stay there (or leave safely).
Trapping: If you fall into the "One-Way Trap," you are very unlikely to climb back out.
Termination: If you are in the "Safe Zone," you will eventually either leave it or get trapped in the "One-Way Trap."

3. The "Scorecards" (Supermartingales)

Once they broke the problem down, they applied existing "scorecards" (mathematical functions) to these smaller zones.

They used a scorecard to prove the "Safe Zone" is actually safe.
They used a different scorecard to prove the "One-Way Trap" really is a trap (you can't get out).
They used a third scorecard to prove you will eventually leave the "Safe Zone" or get trapped.

By combining these three simple proofs, they created a complete proof for the complex, infinite game.

4. Why This Matters: "Almost" vs. "Perfect"

The paper makes two distinct claims about how well this works:

The "Perfect" Case (Almost-Sure): If the game is guaranteed to work 100% of the time, this new method can prove it 100% of the time. It's a perfect key for a perfect lock.
The "Real World" Case (Quantitative): In the real world, nothing is 100%. Maybe the game works 99.9% of the time. The authors' method can prove this with arbitrary precision. If you want to know if it works 99.999% of the time, you can get a certificate that proves it. The only "gap" is as small as you want it to be (like a tiny speck of dust).

5. The "Lending Casino" Example

The paper uses a specific example to show this off:

The Setup: A gambler starts with $1. If they win, they get richer. If they lose, they go into debt.
The Twist: If they are in debt, the casino cheats slightly (the coin is biased), making it harder to win back to zero.
The Question: Will the gambler eventually fall into debt and never come back?
The Result: Previous tools couldn't prove this because the math was too messy (the time to get out of debt is theoretically infinite). The authors' new "decomposition" method broke the problem down, found the "Debt" trap, and successfully proved that yes, the gambler will eventually get stuck in debt forever.

Summary

Think of this paper as inventing a new Lego instruction manual. Before, trying to build a complex castle (proving infinite-time properties) was impossible because the instructions were missing. Now, the authors show you that you don't need to build the whole castle at once. You just need to build the foundation, the walls, and the roof separately, prove each part is solid, and then snap them together.

This gives computer scientists the first complete and reliable way to verify that complex, random systems (like self-driving cars or AI algorithms) will behave correctly forever, not just for a short while.

Technical Summary: Complete Supermartingale Certificates for $\omega$ -Regular Properties

Problem Statement
The paper addresses the formal verification of probabilistic systems modeled as time-homogeneous Markov chains over general (potentially uncountable) state spaces. Specifically, it targets the verification of reactivity properties, a class of temporal properties that subsumes Linear Temporal Logic (LTL) and characterizes $\omega$ -regular languages. Reactivity is defined as a finite conjunction of Streett acceptance conditions, where each condition requires that either a set of states $A$ is visited finitely often or a set of states $B$ is visited infinitely often ( $Fin(A) \cup Inf(B)$ ).

While supermartingale certificates have been established as sound and complete tools for almost-sure termination (a specific reactivity property), existing proof rules for general reactivity and $\omega$ -regular properties suffer from a critical limitation: they provide only sufficient conditions. Consequently, these rules may fail to certify systems that actually satisfy the property. Furthermore, previous attempts at completeness for reactivity relied on value functions capable of expressing arbitrary distributions, rendering them difficult to automate. The paper seeks to construct proof rules that are both sound and complete (specifically, scalar-valued) for reactivity, applicable to countably infinite state spaces and general measurable state spaces.

Methodology: Absorbing-Region Decomposition
The core technical contribution is a methodology that decomposes any reactivity property into a collection of simpler, independent obligations. This decomposition relies on the identification of two types of regions for each Streett pair $(A_i, B_i)$ :

A Global Invariant ( $I$ ): A region of the state space that the system remains within with high probability (or probability 1 in the almost-sure case).
Absorbing Regions ( $J_i$ ): For each pair $i$ , a region $J_i \subseteq I \setminus A_i$ that acts as a "trap" where the probability of returning to $A_i$ is strictly less than 1.

The decomposition reduces the verification of the global reactivity property to three distinct types of obligations:

Qualitative Safety: Ensuring that for every $i$ , the probability of returning from $J_i$ to $A_i$ is uniformly bounded below 1 (i.e., $J_i$ is an absorbing region with respect to $A_i$ ).
Almost-Sure Termination: Ensuring that from any state in the invariant $I$ , the system almost-surely terminates into the union of the target set $B_i$ , the absorbing region $J_i$ , and the complement of the invariant $I^c$ .
Quantitative Safety: Establishing a lower bound on the probability that the system remains within the invariant $I$ forever.

The authors prove that for any time-homogeneous Markov chain satisfying a reactivity property, suitable absorbing regions and an invariant always exist. In the general quantitative case, the invariant can be chosen such that its probability of invariance approximates the probability of the reactivity property within an arbitrary $\epsilon$ . In the almost-sure case, the invariant can be chosen to exactly characterize the property.

Key Contributions and Results

Decomposition Theorems: The paper establishes that every reactivity property admits a decomposition into qualitative safety, almost-sure termination, and quantitative safety obligations.
- Theorem 3.7 (Soundness): If a Markov chain admits an invariant $I$ and absorbing regions $J_i$ satisfying specific conditions, the probability of satisfying the reactivity property is at least the probability of remaining in $I$ forever.
- Theorem 3.12 ( $\epsilon$ -Completeness): For any reactivity property with probability $p > 0$ , and any $\epsilon > 0$ , there exist an invariant and absorbing regions such that the probability of invariance is at least $p - \epsilon$ .
- Theorem 3.14 (Almost-Sure Completeness): If the reactivity property holds almost surely (probability 1), there exists an invariant and absorbing regions such that the probability of invariance is exactly 1.
Instantiation with Supermartingale Certificates: The authors instantiate this decomposition using existing sound and complete proof rules for almost-sure termination on countably infinite state spaces. By combining these with standard results on quantitative safety, they derive two new proof rules (Proof Rule #1 and Proof Rule #2) for reactivity.
- These rules utilize scalar-valued supermartingale certificates (value functions) for safety and termination obligations.
- Theorems 4.4–4.6 and 4.8–4.10: These theorems prove that the new proof rules are sound and $\epsilon$ -complete for quantitative reactivity, and fully complete for almost-sure reactivity, specifically for countably infinite state spaces.
Counterexample to Prior Work: The paper demonstrates that prior supermartingale certificates for $\omega$ -regular properties are incomplete. Using the "Lending Casino" example, it shows a case where a system satisfies a reactivity property almost surely, but the expected time to reach a critical state is infinite, causing prior rules (which rely on finite expected values) to fail. The proposed decomposition handles this by separating the safety obligation (bounded return probability) from the termination obligation.

Significance and Claims
The paper claims to provide the first sound and complete supermartingale certificates for almost-sure $\omega$ -regular properties and the first sound and $\epsilon$ -complete certificates for quantitative $\omega$ -regular properties on time-homogeneous Markov chains with countably infinite state spaces.

The significance lies in bridging the gap between stochastic analysis and formal language theory. By proving that reactivity can be decomposed into termination and safety, the authors enable the automation of verification for complex $\omega$ -regular properties using existing techniques for scalar-valued certificates. The authors note that while their completeness guarantees currently apply to countably infinite state spaces, the underlying decomposition strategy is valid for general state spaces, suggesting that extending completeness to uncountable spaces reduces to the problem of certifying almost-sure termination over general spaces. The work does not claim to solve the synthesis of these certificates automatically but provides the theoretical foundation for doing so.