Search papers, labs, and topics across Lattice.
This paper introduces lazy Streett supermartingales and their lexicographic extension to address the limitations of strong global non-negativity in probabilistic program verification. By demonstrating that weak non-negativity can soundly certify almost-sure satisfaction of $\omega$-regular properties, the authors significantly expand the applicability of automated synthesis methods to include a wider range of sampling distributions. Experimental results show a notable improvement in verification success rates, achieving increases of 20.0-23.5 percentage points over traditional strongly non-negative approaches across 170 benchmarks.
Weak non-negativity in supermartingales can boost verification success rates by over 20% in probabilistic programs, challenging the notion that strict constraints are necessary for soundness.
Martingale-based methods are central to probabilistic program verification, but strong global non-negativity requirements can exclude simple certificates from tractable template classes. Relaxing this requirement enlarges the search space for automated synthesis, but naive relaxations are unsound in the probabilistic setting. We introduce lazy Streett supermartingales and their lexicographic extension, showing that weak non-negativity can nevertheless be used soundly to certify almost-sure satisfaction of $\omega$-regular properties with polynomial templates under a broad class of sampling distributions, including all bounded-support distributions. This extends prior weakly non-negative methods from termination to general $\omega$-regular verification. We further give a compositional account of lexicographic certificates in terms of one-dimensional ones. Experiments on 170 polynomial probabilistic-program benchmarks show increases of 20.0-23.5 percentage points in verification success over the strongly non-negative baseline.
