Supermartingale Certificates for Quantitative Omega-regular Verification and Control
Thomas A. Henzinger, Kaushik Mallik, Pouya Sadeghi, Đorđe Žikelić · 2025
Read Supermartingale Certificates for Quantitative Omega-regular Verification and Control by Thomas A. Henzinger, Kaushik Mallik, Pouya Sadeghi, Đorđe Žikelić (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-18833.txt.
Introduction
Thomas Henzinger, Kaushik Mallik, Pouya Sadeghi, and Đorđe Žikelić extend a proof technique for checking random systems in this 2025 paper. The systems are stochastic and run forever, and the properties at stake are omega-regular, the broad class that covers repeated patterns over time. Earlier certificate methods handled only simpler goals, like reaching or avoiding a state, or gave yes-no answers.
Their certificate pairs the system with an automaton that encodes the property, forming what they call a limit-deterministic Büchi supermartingale. It can certify graded, quantitative claims, not just certain ones. The authors also give automatic methods to build such certificates when the system and controller are stated with polynomial inequalities. Experiments solved checking and control tasks that older methods could not reach. The work widens what can be proven about systems that must behave well forever under chance.
Catalog record
| CREATOR | Thomas A. Henzinger, Kaushik Mallik, Pouya Sadeghi, Đorđe Žikelić |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-18833
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Supermartingale Certificates for Quantitative Omega-regular Verification and Control Thomas A. Henzinger, Kaushik Mallik, Pouya Sadeghi, Đorđe Žikelić Abstract We present the first supermartingale certificate for quantitative ω \omega -regular properties of discrete-time infinite-state stochastic systems. Our certificate is defined on the product of the stochastic system and a limit-deterministic Büchi automaton that specifies the property of interest; hence we call it a limit-deterministic Büchi supermartingale (LDBSM). Previously known supermartingale certificates applied only to quantitative reachability, safety, or reach-avoid properties, and to qualitative (i.e., probability 1) ω \omega -regular properties. We also present fully automated algorithms for the template-based synthesis of LDBSMs, for the case when the stochastic system dynamics and the controller can be represented in terms of polynomial inequalities. Our experiments demonstrate the ability of our method to solve verification and control tasks for stochastic systems that were beyond the reach of previous supermartingale-based approaches. 1 Introduction Stochastic (or probabilistic) systems provide a framework for modeling and quantifying uncertainties in computational models. They are ubiquitous in many areas of computer science, including randomized algorithms [ 56 ] , security and privacy protocols [ 8 ] , stochastic networks [ 31 ] , control theory [ 6 ] , and artificial intelligence [ 34 ] . Many of these systems are safety critical in nature; hence formal methods for guaranteeing their correctness have become an important topic of research. While the correctness of stochastic systems can be accomplished using a variety of complementary approaches, such as abstraction-based [ 28 , 65 , 27 , 39 ] , symbolic integration-based [ 33 , 55 , 9 ] , or logical calculi-based methods [ 43 , 36 , 49 ] , there is a growing interest in martingale-based approaches, which do not only guarantee correctness but also provide supermartingale certificates as locally checkable correctness proofs for improving the trustworthiness of stochastic system design. A supermartingale certificate is a mathematical witness that the desired specification is satisfied. Their name is due to their usage of supermartingale processes from probability theory [ 63 ] towards proving properties of stochastic systems. Recent years have seen significant theoretical and algorithmic advances in utilizing supermartingale certificates for reasoning about stochastic systems with a wide range of specifications, such as termination and reachability [ 11 , 16 , 15 , 44 , 2 , 21 , 40 ] , safety [ 13 , 22 , 59 , 60 , 17 , 1 , 62 ] , Büchi and co-Büchi (aka, stability) [ 14 ] , and cost analysis [ 48 , 61 , 18 ] . These certificates have also been used for the synthesis and verification of controllers with respect to reachability [ 30 , 38 ] , safety [ 52 , 58 , 42 , 66 ] , reach-avoid [ 67 , 64 ] , and stability [ 4 ] objectives, and extensions to continuous-time stochastic systems were also considered [ 47 ] . However, existing supermartingale certificates are limited to atomic specifications or to small fragments of logical specification languages. Designing a new, bespoke supermartingale certificate for each complex automaton-based or composite logical specification is not a feasible approach. Ideally, we would like to have a systematic method for designing supermartingale certificates for an entire, rich class of specifications , which captures all different properties that one might care about. The recent work of Abate et al. [ 3 ] has considered this problem and proposed a supermartingale certificate for the general class of \omega -regular specifications. However, their certificate is restricted to properties that hold with probability 1, so-called qualitative specifications. To the best of our knowledge, no supermartingale certificates for quantitative \omega -regular properties have been proposed. That is, existing supermartingale certificates are insufficient for reasoning about whether an \omega -regular specification is satisfied with a probability p\in[0,1] , which would allow the fine-grained probabilistic analysis that is often needed in practice. In this work, we present the first supermartingale certificate for reasoning about the full class of quantitative \omega -regular specifications for discrete-time infinite-state stochastic systems. In order to design our certificate, we use the fact that each \omega -regular language can be represented by a limit-deterministic Büchi automaton (LDBA) [ 25 ] . This allows us to reduce the problem of proving that an \omega -regular specification is satisfied with probability at least p\in[0,1] to the problem of proving that some set of states in the product of the stochastic system and the LDBA is reached infinitely many times with probability at least p . Hence, we call our certificiate a limit-deterministic Büchi supermartingale (LDBSM) . The design of LDBSMs builds upon and significantly generalizes several existing supermartingale certificates for both quantitative and qualitative reasoning about stochastic systems. We supplement our theoretical developments with fully automated algorithms for the verification and control of infinite-state stochastic systems using LDBSMs. Our algorithms apply to the setting in which the system dynamics and the controller can be represented in terms of a system of polynomial inequalities over real-valued variables. We show how the verification problem (i.e., the synthesis of a supermartingale certificate) and the control problem (i.e., the synthesis of a controller together with a supermartingale certificate) can be reduced to solving a system of polynomial inequalities, for which an off-the-shelf SMT solver may be used. Not only does this give rise to the first certificate-based algorithm, but also the first algorithm for the verification and control of general quantitative \omega -regular specifications for polynomial dynamical systems with a general form of stochastic uncertainties. We implemented a prototype of our method and experimentally evaluated it on a number of random walk examples with quantitative \omega -regular specifications. Our results show that our method can reason about a range of quantitative \omega -regular properties, including those that were beyond the reach of prior works. Finally, while our focus is on the verification and control of infinite-state stochastic systems, our LDBSM certificates are applicable to general Borel-measurable stochastic dynamic systems, and hence they naturally extend to probabilistic programs with real- and integer-valued variables. Moreover, our automated synthesis algorithm also extends to polynomial probabilistic programs, similarly to existing works on supermartingale-based verification of probabilistic programs [ 15 , 22 , 17 ] . In short, our contributions are as follows: 1. Theory: Supermartingale certificates. We present limit-deterministic Büchi supermartingales (LDBSMs), the first supermartingale certificate for arbitrary quantitative \omega -regular specifications of discrete-time infinite-state stochastic systems. 2. Automation: Template-based certificate synthesis. We present the first fully automated algorithms for the verification and control of polynomial stochastic dynamical systems with respect to arbitrary quantitaitve \omega -regular specifications. 2 Preliminaries We assume that the reader is familiar with basic notions of probability theory such as probability space, expected value, etc, which can also be found in standard textbooks on probability theory [ 63 ] . For a set S , we use \mathcal{D}(S) to denote the set of all probability distributions over S , and use 2^{S} to denote the set of all subsets of S . 2.1 Stochastic Dynamical Systems and the Problem Statement Stochastic dynamical systems. A discrete-time stochastic dynamical system (SDS) is a tuple \mathcal{S}=\left({\mathcal{X}},\mathcal{U},\mathcal{W},d,f,\text{Init}\right) , where {\mathcal{X}}\subseteq\mathbb{R}^{n} is the state space, \mathcal{U}\subseteq\mathbb{R}^{m} is the control input