FM2021Top-tier venue
On Lexicographic Proof Rules for Probabilistic Termination
Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný, Jiri Zárevúcky, Dorde Zikelic
Abstract
We consider the almost-sure (a.s.) termination problem for probabilistic programs, which are a stochastic extension of classical imperative programs. Lexicographic ranking functions provide a sound and practical approach for termination of non-probabilistic programs, and their extension to probabilistic programs is achieved via lexicographic ranking supermartingales (LexRSMs). However, LexRSMs introduced in the previous work have a limitation that impedes their automation: all of their components have to be non-negative in all reachable states. This might result in LexRSM not existing even for simple terminating programs. Our contributions are twofold: First, we introduce a generalization of LexRSMs which allows for some components to be negative. This standard feature of non-probabilistic termination proofs was hitherto not known to be sound in the probabilistic setting, as the soundness proof requires a careful analysis of the underlying stochastic process. Second, we present polynomial-time algorithms using our generalized LexRSMs for proving a.s. termination in broad classes of linear-arithmetic programs.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
10 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs cites Aiming low is harder: induction for lower bounds in probabilistic program verification
- Quantitative Bounds on Resource Usage of Probabilistic Programs cites Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs
- Quantitative Bounds on Resource Usage of Probabilistic Programs cites Proving almost-sure termination by omega-regular decomposition
- Positive Almost-Sure Termination: Complexity and Proof Rules cites Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs
- Asparagus: Automated Synthesis of Parametric Gas Upper-Bounds for Smart Contracts cites Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs
Cited by top-tier papers10
- Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Dorde ZikelicCAV 2022 · 30 citations
- Quantitative Bounds on Resource Usage of Probabilistic ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Dorde ZikelicOOPSLA 2024 · 16 citations
- Asparagus: Automated Synthesis of Parametric Gas Upper-Bounds for Smart ContractsZhuo Cai, Soroush Farokhnia, Amir Kafshdar Goharshady, S. HitarthOOPSLA 2023 · 16 citations
- Positive Almost-Sure Termination: Complexity and Proof RulesRupak Majumdar, V. R. SathiyanarayanaPOPL 2024 · 12 citations
- Lexicographic Ranking Supermartingales with Lazy Lower BoundsToru Takisaka, Libo Zhang, Changjiang Wang, Jiamou LiuCAV 2024 · 7 citations
Builds on4
- Aiming low is harder: induction for lower bounds in probabilistic program verificationMarcel Hark, Benjamin Lucien Kaminski, Jürgen Giesl, Joost-Pieter KatoenPOPL 2020 · 47 citations
- A modular cost analysis for probabilistic programsMartin Avanzini, Georg Moser, Michael SchaperOOPSLA 2020 · 41 citations
- Intersection types and (positive) almost-sure terminationUgo Dal Lago, Claudia Faggian, Simona Ronchi Della RoccaPOPL 2021 · 21 citations
- Proving almost-sure termination by omega-regular decompositionJianhui Chen, Fei HePLDI 2020 · 19 citations
Related papers
- Sound and Complete Proof Rules for Probabilistic TerminationRupak Majumdar, V. R. SathiyanarayanaPOPL 2025 · 16 citations
- Learning Probabilistic Termination ProofsAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2021 · 26 citations
- Supermartingales for Unique Fixed Points: A Unified Approach to Lower Bound VerificationSatoshi Kura, Hiroshi Unno, Takeshi TsukadaPLDI 2026
- Supermartingales, Ranking Functions and Probabilistic Lambda CalculusAndrew Kenyon-Roberts, C.-H. Luke OngLICS 2021 · 6 citations
- On Higher-Order Probabilistic Verification via the Weighted Relational Model of Linear LogicUgo Dal Lago, Guido Fiorillo, Paolo PistoneLICS 2026
