Traditional model checking works by exhaustively exploring the state space of a system. This is feasible for a light switch (two states) or a simple circuit, but it fails when a system is "infinite." A program might have an unbounded stack, a database might hold an infinite range of values, or a multi-agent system might involve an unknown, arbitrary number of participants.
The research direction across these papers focuses on symbolic verification: representing infinite sets of states as finite mathematical objects—such as logical formulas or automata—and performing computations directly on those representations.
Logic as a Container for Infinity
The most intuitive way to handle an infinite set is to describe it with a rule rather than listing its members. For example, the set of all positive integers is infinite, but the formula $x > 0$ is finite and easy to manipulate.
Eryk Kopczyński and Szymon Toruńczyk pioneered this in LOIS (Looping Over Infinite Sets). LOIS allows programmers to write code that "iterates" over infinite sets. Behind the scenes, the language doesn't actually loop; it translates the operations into first-order formulas and uses SMT (Satisfiability Modulo Theories) solvers to check properties. By treating formulas as first-class citizens, we can verify infinite-state systems using the same high-level logic we use for finite ones.
Automata as Symbolic Representations
When systems have recursive structures, like a program with nested function calls, they are often modeled as pushdown systems. These systems have an infinite state space because their stack can grow without bound.
To verify these, researchers like Matthew Hague and C.-H. Luke Ong use a "saturation" method described in A Saturation Method for the Modal Mu-Calculus. The core intuition is to represent the set of all possible stack configurations as a finite automaton. Even if there are infinitely many possible stacks, the patterns they follow are often "regular." By manipulating the automaton rather than the stacks themselves, we can compute the entire set of configurations that satisfy a complex property, a process known as Global Model Checking.
This approach extends to planning in complex environments. Giuseppe De Giacomo and colleagues show in Imperfect-Information Games and Generalized Planning that pushdown arenas can make planning decidable even when the world is infinitely large, provided the recursive structure (the "stack") is observable.
Parameterized Systems and Array-Based Models
A different kind of infinity arises in parameterized systems, where the number of components (like robots in a swarm or threads in a processor) is not fixed. We want to prove a property holds for any number of agents $N$.
In SMT-based Safety Checking of Parameterized Multi-Agent Systems, Paolo Felli, Alessandro Gianola, and Marco Montali model these as array-based systems. Here, an array index represents an agent's ID, and the value at that index represents the agent's state. By using first-order logic to describe transitions—for instance, "for all indices $i$, if agent $i$ is in state $A$, it can move to state $B$"—they leverage SMT solvers to prove safety for an unbounded number of agents without ever needing to pick a specific value for $N$.
Similarly, Anthony W. Lin and Philipp Rümmer address Liveness of Randomised Parameterised Systems by representing configurations as strings and transitions as transducers. This allows them to symbolically manipulate the infinite state space of randomized protocols.
Bridging Logic and Automata
The final piece of the puzzle is unifying these two symbolic worlds: logic and automata. Luca Geatti, Alessandro Gianola, and Nicola Gigante introduced First-Order Automata (FOA).
In a standard automaton, transitions are explicit edges between circles. In an FOA, the transitions, initial conditions, and acceptance criteria are all defined by first-order formulas. This creates a powerful bridge: it captures the expressivity of First-Order Linear Temporal Logic (FOLTL) while maintaining the algorithmic benefits of automata. It allows us to reason about systems with unbounded data types by characterizing the relationship between the "current" and "next" state symbolically, ensuring that even when the state space is infinite, the description of its behavior remains finite and computable.