A Hierarchy of Supermartingales for $ω$-Regular Verification
For verification of probabilistic systems, the paper provides a hierarchy of certificates that are strictly more powerful and complete for ω-regular properties, enabling automated verification of a broader class of problems.
The paper proposes new supermartingale-based certificates for verifying almost sure satisfaction of ω-regular properties in Markov chains, showing they are strictly more powerful than existing Streett supermartingales. The most powerful certificates (DVSSMs) are proven complete, and a prototype tool synthesizes LexPMSMs, successfully certifying examples that previously could not be handled.
We propose new supermartingale-based certificates for verifying almost sure satisfaction of $ω$-regular properties: (1) generalised Streett supermartingales (GSSMs) and their lexicographic extension (LexGSSMs), (2) distribution-valued Streett supermartingales (DVSSMs), and (3) progress-measure supermartingales (PMSMs) and their lexicographic extension (LexPMSMs). GSSMs, LexGSSMs, and DVSSMs are derived from least-fixed point characterisations of positive recurrence and null recurrence of Markov chains with respect to given Streett conditions; and PMSMs and LexPMSMs are probabilistic extensions of parity progress measures. We study the hierarchy among these certificates and existing certificates, namely Streett supermartingales, by comparing the classes of problems that can be verified by each type of certificates. Notably, we show that our certificates are strictly more powerful than Streett supermartingales. We also prove completeness of GSSMs for positive recurrence and of DVSSMs for null recurrence: DVSSMs are, in theory, the most powerful certificates in the sense that for any Markov chain that almost surely satisfies a given $ω$-regular property, there exists a DVSSM certifying it. We provide a sound and relatively complete algorithm for synthesising LexPMSMs, the second most powerful certificates in the hierarchy. We have implemented a prototype tool based on this algorithm, and our experiments show that our tool can successfully synthesise certificates for various examples including those that cannot be certified by existing supermartingales.