The fundamental challenge in formal verification is reasoning about infinite or indeterminate behavior. Whether a program contains a loop that runs an unknown number of times or a Markov Decision Process (MDP) represents a system that evolves over many steps, we need a way to summarize these iterations without executing them.
A powerful strategy emerging across different domains is to translate these iterative processes into mathematical recurrence relations. By treating the state of a system as a sequence $x_n$, where $n$ is the iteration step, researchers are transforming the search for "loop invariants" into the search for closed-form solutions to equations.
Lifting Loops to Recurrence Relations
In traditional software verification, proving that a loop is "safe" usually requires a loop invariant—a logical property that remains true every time the loop executes. Finding these invariants is notoriously difficult and often requires human intuition.
Fangzhen Lin and Pritom Rajkhowa address this in their work on VIAP 1.1. Instead of asking a user to guess an invariant, their tool automatically translates C program loops into systems of recurrence relations. For example, a loop that increments a variable $x$ and updates $y$ based on $x$ becomes a system of equations defining $x_n$ and $y_n$.
The intuition here is that if we can find a closed-form solution for these recurrences (an algebraic formula that tells us the value of $x$ at any step $n$ without calculating the previous $n-1$ steps), the verification problem becomes a simple algebraic check. If the safety property holds for all $n$, the program is safe. This bypasses the need for "guess-work" induction and replaces it with automated algebraic solving.
The Distinction Between Chance and Mass
This recurrence-based perspective extends beyond deterministic code into probabilistic systems like Markov Decision Processes. In Chance and Mass Interpretations of Probabilities in Markov Decision Processes, Yun Chen Tsai, Kittiphon Phalakarn, S. Akshay 0001, and Ichiro Hasuo demonstrate that how we interpret iteration changes the mathematical difficulty of the problem.
They distinguish between two semantics:
- Chance: The standard view where a system follows one path based on a coin toss.
- Mass: A view where a "population" or "resource" is split and distributed across states simultaneously.
While "chance" reachability can often be solved with linear programming in polynomial time, "mass" reachability behaves like a recurrence sequence. In the mass interpretation, the amount of resource in a state at step $n$ is defined by the sum of resources in preceding states, weighted by transition probabilities. This creates a linear recurrence sequence.
The Fundamental Barrier of Sequence Analysis
The reason this research direction is so critical—and so difficult—is that it eventually hits a hard mathematical wall: the Skolem Problem.
The Skolem Problem asks if a term in a linear recurrence sequence will ever exactly equal zero. Despite its simple framing, it remains one of the most famous unsolved problems in mathematics. As Tsai and colleagues point out, mass-based reachability in MDPs is at least as hard as the Skolem problem, and in some cases, it is entirely undecidable.
Similarly, Lin and Rajkhowa note that determining if a general recurrence has a closed-form solution is undecidable. When automated solvers fail to find these solutions, verification tools must fall back on weaker induction techniques.
Why This Works
The power of this direction lies in its ability to unify disparate fields. By framing both program loops and probabilistic transitions as sequences:
- Automation: We can leverage decades of progress in computer algebra and recurrence solvers to find invariants automatically.
- Precision: We move from "approximate" or "bounded" verification (checking only the first 100 steps) to "unbounded" verification (proving a property for all $n$).
- Clarity: It exposes the shared mathematical root of why certain verification problems are easy (chance-based MDPs) and others are potentially impossible (mass-based MDPs or complex nested loops).
By reducing the "ghost in the machine" of iteration to the concrete language of sequences, these researchers are mapping the exact boundaries of what can be automatically proven about complex systems.