Lune

ICSE2023Top-tier venue

Data-driven Recurrent Set Learning For Non-termination Analysis

Zhilei Han, Fei He

Abstract

Termination is a fundamental liveness property for program verification. In this paper, we revisit the problem of non-termination analysis and propose the first data-driven learning algorithm for synthesizing recurrent sets, where the non-terminating samples are effectively speculated by a novel method. To ensure convergence of learning, we develop a learning algorithm which is guaranteed to converge to a valid recurrent set if one exists, and thus establish its relative completeness. The methods are implemented in a prototype tool, and experimental results on public benchmarks show its efficacy in proving non-termination as it outperforms state-of-the-art tools, both in terms of cases solved and performance. Evaluation on non-linear programs also demonstrates its ability to handle complex programs.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

its abstract · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Non-termination Witnesses and Their ValidationZsófia Ádám, Paulína Ayaziová, Levente Bajczi, Dirk Beyer et al.ASE 2025 · 2 citations

Related papers

  1. Data-Driven Loop Bound Learning for Termination AnalysisRongchen Xu, Jianhui Chen, Fei HeICSE 2022 · 6 citations
  2. DynamiTe: dynamic termination and non-termination proofsTon Chanh Le, Timos Antonopoulos, Parisa Fathololumi, Eric Koskinen et al.OOPSLA 2020 · 26 citations
  3. Accurate Inference of Termination ConditionsBiting Huang, Zhilei Han, Fei HeICSE 2026
  4. LLM-Guided Loop Bound Generation for Program Termination VerificationZan Gong, Biting Huang, Fei HeICML 2026
  5. Decision Tree Learning in CEGIS-Based Termination AnalysisSatoshi Kura, Hiroshi Unno, Ichiro HasuoCAV 2021 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines