Lune

PLDI2021Top-tier venue

Termination analysis without the tears

Shaowei Zhu, Zachary Kincaid

Abstract

Determining whether a given program terminates is the quintessential undecidable problem. Algorithms for termination analysis may be classified into two groups: (1) algorithms with strong behavioral guarantees that work in limited circumstances (e.g., complete synthesis of linear ranking functions for polyhedral loops), and (2) algorithms that are widely applicable, but have weak behavioral guarantees (e.g., Terminator). This paper investigates the space in between: how can we design practical termination analyzers with useful behavioral guarantees?

This paper presents a termination analysis that is both compositional (the result of analyzing a composite program is a function of the analysis results of its components) and monotone ("more information into the analysis yields more information out"). The paper has two key contributions. The first is an extension of Tarjan's method for solving path problems in graphs to solve infinite path problems. This provides a foundation upon which to build compositional termination analyses. The second is a collection of monotone conditional termination analyses based on this framework. We demonstrate that our tool ComPACT (Compositional and Predictable Analysis for Conditional Termination) is competitive with state-of-the-art termination tools while providing stronger behavioral guarantees.

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.

13 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

  • Using graph neural networks for program termination cites Neural termination analysis
  • Neural termination analysis cites Using graph neural networks for program termination
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers13

  1. Sound and Complete Proof Rules for Probabilistic TerminationRupak Majumdar, V. R. SathiyanarayanaPOPL 2025 · 16 citations
  2. Neural termination analysisMirco Giacobbe, Daniel Kroening, Julian ParsertFSE 2022 · 16 citations
  3. Exploiting the Sparseness of Control-Flow and Call Graphs for Efficient and On-Demand Algebraic Program AnalysisGiovanna Kobus Conrado, Amir Kafshdar Goharshady, Kerim Kochekov, Yun Chen Tsai et al.OOPSLA 2023 · 12 citations
  4. Solvable Polynomial Ideals: The Ideal Reflection for Program AnalysisJohn Cyphert, Zachary KincaidPOPL 2024 · 11 citations
  5. Using graph neural networks for program terminationYoav Alon, Cristina DavidFSE 2022 · 9 citations

Related papers

  1. A Categorical Basis for Robust Program AnalysisZachary Kincaid, Shaowei ZhuPLDI 2026
  2. Non-termination Proving at ScaleAzalea Raad, Julien Vanegue, Peter W. O'HearnOOPSLA 2024 · 10 citations
  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 Termination and Non-termination Analysis of C Programs with Bit-Precise Bounded Semantics and Advanced ConstructsNegar Fathi, Hiroshi Unno, Tachio Terauchi, Rahul PurandareFSE 2026
  5. EndWatch: A Practical Method for Detecting Non-Termination in Real-World SoftwareYao Zhang, Xiaofei Xie, Yi Li, Sen Chen et al.ASE 2023 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines