💻 computer science

Termination analysis with interpolation-based transition invariant generation

This paper presents a unified termination analysis framework that leverages Craig interpolation to generate well-founded transition invariants, thereby enabling the simultaneous proof of both termination and nontermination for infinite-state systems with performance comparable to state-of-the-art tools.

Original authors: Konstantin Britikov, Martin Blicha, Grigory Fedyukovich, Natasha Sharygina

Published 2026-08-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Konstantin Britikov, Martin Blicha, Grigory Fedyukovich, Natasha Sharygina

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Great Computer Escape Hunt

Imagine you are watching a robot play a game of "follow the leader" inside a giant, infinite maze. The robot starts at a specific spot and follows a set of rules to move from one room to the next. The big question computer scientists ask is: Will this robot eventually get tired and stop moving, or will it run forever, trapped in an endless loop? This is the problem of "termination analysis." It's a fundamental puzzle in the world of formal methods, a branch of computer science dedicated to proving that software behaves exactly as we expect.

To understand the stakes, think of the two possible outcomes. If the robot stops, it means the program is "safe" and will finish its job. If it runs forever, it's "non-terminating," which usually means a bug that freezes a system. For a long time, scientists treated these two outcomes as completely separate mysteries. They had one set of tools to prove a robot would stop (like finding a countdown timer that always goes down) and a totally different set of tools to prove it wouldn't stop (like finding a room where the robot gets stuck in a circle). But just like a detective needs to know both how a crime happened and how it didn't to solve a case, computer scientists realized that understanding why a program stops and why it doesn't are two sides of the same coin. The challenge was to build a single detective agency that could solve both mysteries at once.

The Paper's Big Idea: A Detective with Two Hats

In this paper, the authors—Konstantin Britikov, Martin Blicha, Grigory Fedyukovich, and Natasha Sharygina—introduce a clever new way to solve this puzzle. They built a unified framework that lets the tools for proving "stop" and "don't stop" talk to each other and share clues. Their approach is like a detective who doesn't just look for the culprit but also studies the crime scene to understand how the crime didn't happen, using that knowledge to solve the case faster.

The core of their method is something called "interpolation-based transition invariant generation." That sounds like a mouthful, so let's break it down with a story. Imagine the robot leaves a trail of footprints as it moves through the maze. Sometimes, the robot hits a dead end (a "sink state") and stops. The authors' algorithm looks at these "dead-end" trails. Instead of just saying, "Okay, it stopped here," they use a mathematical trick called Craig interpolation to generalize the story. They ask: "What is the reason the robot stopped? Was it because the battery died? Was it because the floor was slippery?"

By analyzing the footprints of the robot that did stop, the algorithm constructs a "rule of the road" (a transition invariant) that explains why the robot must stop. It's like realizing, "Ah, every time the robot turns left, it loses a step of energy, and since it starts with limited energy, it can't run forever." This rule is a "well-founded transition invariant," which is a fancy way of saying a guarantee that the robot is getting closer to the finish line with every move.

But here is the magic twist: the algorithm doesn't just stop there. It uses this "stop rule" to help hunt for the "don't stop" cases. If the robot doesn't stop, it means the "stop rule" doesn't cover every possible path the robot could take. The algorithm then focuses its attention specifically on the parts of the maze the rule missed. It asks, "Okay, we know the robot stops if it goes left, but what if it goes right?" It then runs a separate check to see if going right leads to an endless loop. If it does, the robot is non-terminating. If it doesn't, the algorithm adds this new path to its "stop rule" and tries again.

This back-and-forth is the paper's main breakthrough. Instead of running two separate programs—one to prove stopping and one to prove looping—they run one smart program that uses the results of one to guide the other. If the "stop" proof is weak, the "loop" proof steps in to find the missing pieces. If the "loop" proof finds a safe path, the "stop" proof uses that to build a stronger rule.

What They Found and How Sure They Are

The authors implemented this idea in a tool called GOLEM and tested it on a massive collection of puzzles called the "Termination Competition" benchmarks. These are standard tests used by experts to see how good different tools are at solving these infinite-state problems.

The results were quite promising. The new tool, which they call ITPTIG+, managed to solve 761 of the benchmark problems. This is a significant improvement over their older version (SNA), which only solved 343. More importantly, ITPTIG+ solved 240 problems that neither of their previous tools could solve on their own. This suggests that combining the two types of analysis really does make the detective work more efficient.

When they compared their tool to the current champions in the field (tools named KOAT, LOAT, and T2), ITPTIG+ held its own. It solved 8 unique problems that none of the other top tools could solve. Two of these unique solutions were problems that had never been solved by any tool in the history of the Termination Competition. The authors are confident in these results because they are based on actual mathematical proofs generated by the tool, not just guesses or simulations. They proved that if their tool says "Terminating," the system definitely stops, and if it says "Non-terminating," the system definitely loops forever.

However, the paper also admits where the method hits a wall. There are still some complex systems where the tool returns "UNKNOWN." This happens when the robot's path is so complicated that the "stop rule" the algorithm builds doesn't cover every possible scenario, and the "loop" check can't find a clear endless cycle either. It's like a detective who has a great theory about the crime but can't quite find the final piece of evidence to close the case.

In short, this paper shows that by letting the "stop" and "don't stop" detectives work together, we can solve more computer puzzles than ever before. It doesn't solve every problem in the universe, but it proves that sharing clues between these two sides of the problem is a powerful strategy that gets us closer to making our software safer and more reliable.

Technical Summary: Termination Analysis with Interpolation-based Transition Invariant Generation

Problem Statement

The termination and non-termination analysis of infinite-state systems are complementary problems that are typically addressed by separate techniques. While proving termination often relies on ranking functions or disjunctively well-founded transition invariants, non-termination analysis predominantly focuses on detecting recurrent sets (sets of states from which execution cannot escape). Existing methods, such as Safety-based Non-termination Analysis (SNA), treat these as distinct problems. SNA iteratively refines safety problems to prove non-termination or returns "UNKNOWN" if it cannot conclude, but it lacks a mechanism to prove termination when it fails to find a recurrent set. This paper addresses the need for a unified framework that connects these two analyses, allowing them to share intermediate results and guide one another.

Methodology

The authors propose a unified framework that extends SNA to prove termination by generating well-founded transition invariants using Craig interpolation. The core methodology involves the following components:

1. Unified Framework Architecture

The approach integrates termination and non-termination analysis into a single loop. It utilizes the terminating transition traces constructed by SNA (when a safety check fails) as a source of structural information. Instead of merely blocking these traces to refine the safety problem, the algorithm generalizes them into transition invariants.

2. Interpolation-based Transition Invariant Generation (TRINVGEN)

The central innovation is a procedure, TRINVGEN, which generates a disjunctively well-founded transition invariant candidate from a terminating trace. The process involves five steps:

Computation of $NT_n$ : The algorithm computes a formula encoding states from which non-sink states can be reached within $n$ transitions.
Interpolation: A Craig interpolant is computed between the trace formula and the negation of $NT_n$ (combined with the negation of sink states). This interpolant over-approximates the trace and captures the structural reasons for termination.
DNF Under-approximation: The interpolant is converted into a Disjunctive Normal Form (DNF) formula. To avoid exponential blowup, an on-demand approach is used where disjuncts are constructed based on SMT solver models.
Filtering: Each disjunct is checked for well-foundedness by synthesizing a linear ranking function. Only disjuncts admitting a ranking function are preserved to form the candidate transition invariant.
Coverage Synthesis: The algorithm computes a coverage formula $C(X)$ , encoding the set of states for which the candidate transition invariant is valid.

3. Iterative Analysis and Self-Guidance

The main analysis loop (Algorithm 4 and its extension, Algorithm 5) operates as follows:

Safety Check: The system performs a safety check on the current problem.
Unsat Case (Terminating Trace Found): If a trace to a sink state is found, TRINVGEN produces a transition invariant candidate and a coverage formula $C$ $C$ .
- The algorithm then checks if the states not covered by the invariant ( $\neg C$ ) are reachable.
- If $\neg C$ is unreachable, the invariant covers all reachable states, and the system is proven terminating.
- If $\neg C$ is reachable, the algorithm refines the problem by blocking states that deterministically lead to termination (via BLOCKTERM) and pushes new sub-problems to analyze the uncovered states.
Sat Case (Recurrent Set Found): If the safety check returns "SAFE" with an inductive invariant, the algorithm checks if this invariant is a recurrent set. If so, the system is non-terminating.
Stack-based Extension (Algorithm 5): To handle complex cases where a single invariant does not cover the entire state space, the extended algorithm maintains a stack of safety problems. It focuses analysis on specific reachable states ( $S_m$ ) where the current invariant is invalid, attempting to extend the invariant or prove non-termination for these specific regions.

Key Contributions

The paper presents three primary contributions:

Novel Interpolation-based Generation: A method for generating disjunctively well-founded transition invariants using Craig interpolation to capture termination reasons from traces.
Unified Analysis Procedure: A framework that unifies termination and non-termination analysis, utilizing intermediate results (traces and invariants) for self-guidance. This allows the termination proof to focus on uncovered states and the non-termination proof to benefit from the structural insights of termination traces.
Implementation and Evaluation: Implementation within the GOLEM verification framework and evaluation on Integer Transition Systems benchmarks from the Termination Competition.

Experimental Results

The authors evaluated their tool, ITPTIG+, against the classical SNA, the intermediate ITPTIG, and state-of-the-art tools (KOAT, LOAT, T2) on 1,200 Integer Transition System benchmarks.

Performance vs. Classical SNA: ITPTIG+ solved 761 instances, significantly outperforming SNA (343 instances) and ITPTIG (521 instances). It uniquely solved 240 instances that neither SNA nor ITPTIG could solve.
Performance vs. State-of-the-Art: While T2 solved the most instances overall (1002), ITPTIG+ was competitive and uniquely solved 8 instances that no other tool in the comparison solved. Notably, two of these instances (juLinkedListCreateAddAll.jar-obl-11 and juLinkedListCreateAddAllAt.jar-obl-17) had never been solved by any tool in the Termination Competition prior to this work.
Non-termination: The tool demonstrated significant improvement in non-termination analysis compared to classical SNA by focusing recurrent set detection on specific uncovered state regions.

Significance and Claims

The paper claims that combining termination and non-termination reasoning is beneficial, yielding performance comparable to state-of-the-art tools while solving unique instances. The significance lies in the unification of these previously separate problems within a single framework. By using Craig interpolation to generalize terminating traces, the approach captures structural reasons for termination and uses them to guide the analysis of the entire transition system. The authors emphasize that grounding the approach in safety verification provides a robust foundation, enabling efficient checking of both properties via existing safety solvers. The work demonstrates that intermediate results from one type of analysis (e.g., traces from a failed safety check) can effectively drive the other (e.g., invariant generation for termination), creating a synergistic effect that improves overall verification capabilities.