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.
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
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
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.· Proceedings of the ACM on Pr...· 0 citations
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...
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.
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.