Complete $\omega$-Regular Supermartingale Certificates

Alessandro Abate; Diptarko Roy; Mirco Giacobbe; Sergey Ichtchenko

arxiv: 2605.21134 · v2 · pith:UKYN33HPnew · submitted 2026-05-20 · 💻 cs.LO

Complete ω-Regular Supermartingale Certificates

Alessandro Abate , Mirco Giacobbe , Sergey Ichtchenko , Diptarko Roy This is my paper

Pith reviewed 2026-05-21 01:40 UTC · model grok-4.3

classification 💻 cs.LO

keywords supermartingalesreactivity propertiesω-regular propertiesMarkov chainsalmost-sure terminationproof rulestemporal logicverification

0 comments

The pith

Reactivity properties on Markov chains decompose into almost-sure termination obligations to absorbing regions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that every reactivity property, which captures ω-regular properties and subsumes linear temporal logic, admits a decomposition into multiple almost-sure termination obligations directed at absorbing regions. It proves that suitable absorbing regions exist for any time-homogeneous Markov chain, even with general state spaces. This reduction converts any complete proof rule for almost-sure termination into a complete rule for reactivity in the almost-sure case and an ε-complete rule in the quantitative case. A sympathetic reader would care because the result lets existing termination certificates, such as supermartingales, now certify full temporal behaviors on countably infinite state spaces.

Core claim

Every reactivity property admits decomposition into multiple obligations of almost-sure termination into absorbing regions, and appropriate absorbing regions always exist on general state spaces. This enables the extension of every complete proof rule for almost-sure termination into a proof rule for reactivity that is complete in the almost-sure case, and complete up to an arbitrarily small ε-approximation in the quantitative case. Applied to supermartingales, the approach produces the first sound and complete supermartingale certificates for almost-sure ω-regular properties and the first sound and ε-complete supermartingale certificates for quantitative ω-regular properties on time-homog

What carries the argument

the decomposition of reactivity properties into almost-sure termination obligations into absorbing regions

If this is right

Every complete proof rule for almost-sure termination extends to a complete proof rule for reactivity.
Supermartingale certificates for almost-sure termination become sound and complete certificates for almost-sure ω-regular properties on countably infinite state spaces.
Quantitative supermartingales become sound and ε-complete certificates for quantitative ω-regular properties.
Standard quantitative safety results extend to quantitative reactivity via the same construction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same decomposition technique could be tested on non-countable or uncountable state spaces to check whether the existence of absorbing regions remains guaranteed.
One could explore whether the number of required absorbing regions can be bounded for common reactivity patterns such as fairness or persistence.
The approach suggests a route to lift other termination certificates, such as ranking functions, to full ω-regular verification without new machinery.

Load-bearing premise

For any reactivity property on a time-homogeneous Markov chain with general state space, appropriate absorbing regions exist that allow decomposition into almost-sure termination obligations.

What would settle it

A concrete reactivity property together with a time-homogeneous Markov chain on which no absorbing regions exist that permit the required decomposition into almost-sure termination obligations.

read the original abstract

We introduce a general methodology for the construction of sound and complete proof rules for the almost-sure and quantitative acceptance of reactivity properties on time-homogeneous Markov chains with general state spaces. Reactivity captures the $\omega$-regular properties and subsumes linear temporal logic. Our core technical result establishes that every reactivity property admits decomposition into multiple obligations of almost-sure termination into absorbing regions, and that appropriate absorbing regions always exist on general state spaces. This enables the extension of every complete proof rule for almost-sure termination into a proof rule for reactivity that is complete in the almost-sure case, and complete up to an arbitrarily small $\varepsilon$-approximation in the quantitative case. We apply our new methodology to recent results on sound and complete supermartingale certificates for almost-sure termination in the special case of countably infinite state spaces, alongside standard results on quantitative safety. As a result, we obtain the first sound and complete supermartingale certificates for almost-sure $\omega$-regular properties and the first sound and $\varepsilon$-complete supermartingale certificates for quantitative $\omega$-regular properties on time-homogeneous Markov chains with countably infinite state spaces.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper lifts complete supermartingale termination certificates to ω-regular properties via a decomposition into absorbing regions, but the claimed generality on arbitrary state spaces rests on an existence result whose measurability details are not obvious from the abstract.

read the letter

The core contribution is a decomposition that turns any reactivity property into a finite set of almost-sure termination obligations to absorbing regions, plus the claim that such regions always exist on general state spaces. This lets the authors reuse recent complete supermartingale rules for termination and obtain the first sound-and-complete certificates for almost-sure ω-regular properties, and sound-plus-ε-complete ones for the quantitative case, on countably infinite chains. That extension is the actual new piece; the rest follows by plugging in prior termination results and standard quantitative safety facts. The write-up is direct about what is being reused and what is being added, which makes the logic easy to follow. The countable-state application looks workable on the surface. The soft spot is the existence claim for absorbing regions. The abstract states that appropriate regions always exist, yet it does not list the measure-theoretic or topological conditions needed to keep the regions measurable, the subprocesses Markov, and the supermartingales well-defined. If the construction relies on arbitrary choice of sets that fail these requirements, the completeness argument does not go through for truly general spaces. The stress-test note correctly flags this gap; without the full derivations it is impossible to see whether the paper supplies the missing regularity assumptions or works only under implicit standard-Borel restrictions. The quantitative ε-completeness part also needs explicit error-bound tracking that is only sketched. This work is aimed at people who already use supermartingales or ranking functions for probabilistic verification of infinite-state systems. A reader who wants a general way to move from termination certificates to full LTL-style properties will find the decomposition technique useful even if the generality claim needs tightening. I would send it to peer review because the claimed advance is substantial and the method is modular enough that referees can check the critical existence step without starting from scratch.

Referee Report

1 major / 2 minor

Summary. The paper introduces a general methodology for sound and complete supermartingale certificates for almost-sure and quantitative acceptance of reactivity (ω-regular) properties on time-homogeneous Markov chains with general state spaces. The core technical result asserts that every reactivity property decomposes into finitely many almost-sure termination obligations into absorbing regions, which are shown to always exist; this allows every complete termination certificate to be lifted to a complete (or ε-complete) certificate for reactivity. The approach is instantiated on recent supermartingale results for countable state spaces, yielding the first such certificates for almost-sure and quantitative ω-regular properties.

Significance. If the central decomposition and existence claims hold, the work provides a reusable bridge from termination analysis to full ω-regular verification, with explicit completeness guarantees. The decomposition into absorbing-region termination obligations is a clean technical contribution that preserves soundness and completeness (up to ε in the quantitative case). The application to countable spaces produces novel certificates that were previously unavailable.

major comments (1)

[Core technical result / existence theorem] Core technical result (abstract and the existence theorem): the claim that 'appropriate absorbing regions always exist on general state spaces' is load-bearing for completeness, yet the construction does not explicitly verify that the chosen regions are measurable with respect to the underlying σ-algebra. Without this, the induced subprocesses may fail to remain Markovian and the almost-sure termination obligations cannot be expressed via supermartingales in the required sense. A concrete counter-example construction or an additional regularity assumption (e.g., standard Borel) is needed to close the gap.

minor comments (2)

[Introduction] The distinction between the fully general state-space theorem and the countable-space instantiation is not always sharp in the introduction; a short paragraph clarifying which results require only countability would improve readability.
[Preliminaries] Notation for reactivity properties and absorbing regions is introduced gradually; a single consolidated table or definition block early in the paper would help readers track the decomposition.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the importance of measurability in the core construction. We address the single major comment below and will incorporate a clarification to strengthen the presentation.

read point-by-point responses

Referee: Core technical result (abstract and the existence theorem): the claim that 'appropriate absorbing regions always exist on general state spaces' is load-bearing for completeness, yet the construction does not explicitly verify that the chosen regions are measurable with respect to the underlying σ-algebra. Without this, the induced subprocesses may fail to remain Markovian and the almost-sure termination obligations cannot be expressed via supermartingales in the required sense. A concrete counter-example construction or an additional regularity assumption (e.g., standard Borel) is needed to close the gap.

Authors: We appreciate the referee drawing attention to this point. The absorbing regions in our decomposition are constructed as the sets of states from which there exists a scheduler ensuring that the ω-regular reactivity condition is satisfied by reaching designated absorbing components. Because the reactivity property is expressed via a measurable acceptance set on path space and the transition kernel is measurable, these regions arise as the greatest fixed points of measurable set-valued operators and are therefore measurable with respect to the given σ-algebra. Consequently the restricted subprocesses remain time-homogeneous Markov chains. We will add an explicit lemma (and its proof) in the revised manuscript that verifies this measurability directly from the construction, thereby confirming that the almost-sure termination obligations are well-defined and that the supermartingale certificates apply without change. No additional regularity assumption such as standard Borel spaces is required, and we do not believe a counter-example exists under the stated hypotheses. revision: yes

Circularity Check

0 steps flagged

No circularity: core existence result and decomposition are independent of the termination certificates being extended

full rationale

The paper's central technical result asserts that every reactivity property decomposes into almost-sure termination obligations into absorbing regions that always exist on general state spaces. This is presented as a new contribution that then enables extension of prior complete termination proof rules (applied to recent supermartingale results for countably infinite spaces). No equation or definition in the provided abstract reduces the existence claim or completeness to a self-referential fit, renaming, or load-bearing self-citation chain; the termination results are treated as independent inputs whose completeness is presupposed rather than redefined. The derivation chain therefore remains self-contained against external benchmarks for termination.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of suitable absorbing regions for every reactivity property and on the prior soundness and completeness of termination certificates; these are domain assumptions rather than new free parameters or invented entities.

axioms (1)

domain assumption Time-homogeneous Markov chains admit absorbing regions for any reactivity property such that the property decomposes into almost-sure termination obligations.
Invoked as the core technical result enabling the extension of termination rules to reactivity.

pith-pipeline@v0.9.0 · 5740 in / 1393 out tokens · 29872 ms · 2026-05-21T01:40:06.817058+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Value Functions as Supermartingale Certificates
cs.LG 2026-05 unverdicted novelty 7.0

Value functions of policies satisfying ω-regular properties encode Streett supermartingale certificates under appropriate rewards.