Lune

PLDI2020Top-tier venue

Proving almost-sure termination by omega-regular decomposition

Jianhui Chen, Fei He

Abstract

Almost-sure termination is the most basic liveness property of probabilistic programs. We present a novel decomposition-based approach for proving almost-sure termination of probabilistic programs with complex control-flow structure and non-determinism. Our approach automatically decomposes the runs of the probabilistic program into a finite union of ω-regular subsets and then proves almost-sure termination of each subset based on the notion of localized ranking supermartingales. Compared to the lexicographic methods and the compositional methods, our approach does not require a lexicographic order over the ranking supermartingales as well as the so-called unaffecting condition. Thus it has high generality. We present the algorithm of our approach and prove its soundness, as well as its relative completeness. We show that our approach can be applied to some hard cases and the evaluation on the benchmarks of previous works shows the significant efficiency of our approach.

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.

8 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Supermartingales, Ranking Functions and Probabilistic Lambda Calculus cites On probabilistic termination of functional programs with continuous distributions
  • On probabilistic termination of functional programs with continuous distributions cites Supermartingales, Ranking Functions and Probabilistic Lambda Calculus
  • Quantitative Bounds on Resource Usage of Probabilistic Programs cites Supermartingales, Ranking Functions and Probabilistic Lambda Calculus
  • Quantitative Bounds on Resource Usage of Probabilistic Programs cites On Lexicographic Proof Rules for Probabilistic Termination
  • Quantitative Bounds on Resource Usage of Probabilistic Programs cites On probabilistic termination of functional programs with continuous distributions
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers8

  1. Quantitative Bounds on Resource Usage of Probabilistic ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Dorde ZikelicOOPSLA 2024 · 16 citations
  2. On probabilistic termination of functional programs with continuous distributionsRaven Beutner, Luke OngPLDI 2021 · 12 citations
  3. On Lexicographic Proof Rules for Probabilistic TerminationKrishnendu Chatterjee, Ehsan Kafshdar Goharshady, Petr Novotný, Jiri Zárevúcky et al.FM 2021 · 11 citations
  4. Supermartingales, Ranking Functions and Probabilistic Lambda CalculusAndrew Kenyon-Roberts, C.-H. Luke OngLICS 2021 · 6 citations
  5. Automated Expected Value Analysis of Recursive ProgramsMartin Avanzini, Georg Moser, Michael SchaperPLDI 2023 · 6 citations

Related papers

  1. Lexicographic Ranking Supermartingales with Lazy Lower BoundsToru Takisaka, Libo Zhang, Changjiang Wang, Jiamou LiuCAV 2024 · 7 citations
  2. Supermartingales for Unique Fixed Points: A Unified Approach to Lower Bound VerificationSatoshi Kura, Hiroshi Unno, Takeshi TsukadaPLDI 2026
  3. Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Dorde ZikelicCAV 2022 · 30 citations
  4. Sound and Complete Proof Rules for Probabilistic TerminationRupak Majumdar, V. R. SathiyanarayanaPOPL 2025 · 16 citations
  5. Learning Probabilistic Termination ProofsAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2021 · 26 citations
Dusk over the sea between two cliffs drawn in fine vertical lines