Skip to content
Preprint

Polynomial Invariants for Probabilistic Transition Systems with Unbounded Support

Sep 2026 · 0 citations · 41 references
Computer Science

TL;DR

If all random samples have finite moments and the authors can verify a moment bound on the runtime of a linear loop, then they can automatically synthesise polynomial loop invariants that satisfy the OST and simplify the dui property to proving finiteness of the expected value of an expression depending on the update matrix, the degree of the martingale expression, and the stopping time.

Abstract

We study the synthesis of polynomial invariants for probabilistic transition systems (PTS) based on martingale theory. We present tractable methods to verify that such polynomials are indeed invariants, in the sense that their expected value upon termination is the same as their value at the start of the computation. We do this by applying the Optional Stopping Theorem (OST) in the form of a specific precondition. This precondition requires the existence of an integrable dominating function for the martingale expression, which implies uniform integrability; we refer to this condition as dui. For linear PTS we simplify the dui property to proving finiteness of the expected value of an expression depending on the update matrix, the degree of the martingale expression, and the stopping time. Specifically, if all random samples have finite moments and we can verify a moment bound on the runtime of a linear loop, then we can automatically synthesise polynomial loop invariants that satisfy the OST. Notably, dui allows for the sampled distributions to have unbounded support, which is a novel contribution to the field.

View source

Similar papers

Preprint Sep 2026

Quantitative coverability for probabilistic well-structured transition systems

Well-structured transition systems (WSTS) provide a classical framework for the verification of infinite-state systems, but their probabilistic extensions lack a unified treatment of quantitative coverability: path-enumeration algorithms assume a finite branching degree, while alternative approximation schemes defer so...

Raphaëlle Faure, Alain Finkel, Gaspard Fougea et al. · 0 citations
Preprint Oct 2026

Decreasing Diagrams are Complete for Confluence

It is proved that every confluent transition system admits a locally decreasing labeling using only three labels, which can, in principle, certify the confluence of every confluent system, and hence of every confluent program.

J. Endrullis, Ievgen Ivanov, F. van Raamsdonk · 0 citations
Open access Aug 2026

Type-Directed Discretization of Probabilistic Programs

The empirical evaluation shows two complementary strengths of Slice when paired with discrete backends: it enables exact inference for challenging continuous programs that lie beyond the reach of previous exact systems, and is competitive with state-of-the-art exact inference systems for continuous programs.

Katherine Wu, Jules Jacobs, Kevin Batz et al. · 0 citations
Preprint Sep 2026

Discrete-time polynomial systems with inputs and outputs: structure, reachability, observability, and minimal realizations

We study the realization problem for discrete-time input/output polynomial systems. These are formalized using tools from commutative algebra and algebraic geometry as systems whose state spaces are algebraic varieties, or more abstractly the set of k-points of an affine k-scheme, where k is an arbitrary infinite field...

Eduardo Sontag · 0 citations
#edge computing Preprint Sep 2026

Automatic constraints with few subpowers and graphoid recognition

For graphoid automata, these results give polynomial-time recognition without a graph-width restriction, effective boundary composition, and comparison of finite graph relations, and the quadratic boundary bounds are optimal in the worst case.

Antonios Kalampakas · 0 citations
Preprint Oct 2026

The smallest programmable machine and the hardness of analyzing it

This work provides an explicit construction of a three-pebble automaton U capable of simulating any deterministic finite automaton (DFA) on a given input word, establishing a link between pebble automata capabilities, Kolmogorov complexity, and automatic complexity.

J. Montoya · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.