Many real-world computing systems possess an infinite number of possible states. Consider a recursive program whose call stack can grow arbitrarily deep, a database tracking unbounded integer records, or a concurrent protocol operating under relaxed hardware memory models. Exhaustive testing or explicit state enumeration is fundamentally impossible in these domains, a limitation highlighted by Shaukat Ali et al. in Editorial to the theme section on model-based testing. To validate or reason about such systems, we must shift from tracking individual concrete states to manipulating symbolic representations of infinite state sets.
The core insight across this research direction is that infinite sets of configurations often possess a regular structural pattern that can be captured by finite automata. By encoding infinite state spaces as formal languages, we can leverage the rich mathematical toolkit of automata theory to perform exact, decidable computations over infinite domains.
Encoding Infinite States as Regular Languages
How can a finite machine represent an infinite set of configurations? The trick lies in how we encode a system's state.
In a pushdown system (which models recursive function calls), a configuration consists of a control state and the current stack contents. Because a stack is inherently a sequence of symbols, the set of all possible stack configurations can be treated as a language. Crucially, as noted by Nathalie Bertrand et al. in CONCUR Test-Of-Time Award 2021 (Invited Paper), regular automata can be employed to represent these state sets, making predecessor operators computable for infinite-state systems.
Matthew Hague et al. expanded this principle to higher-order pushdown systems in Symbolic Backwards-Reachability Analysis for Higher-Order Pushdown Systems, proving that the set of configurations capable of reaching a target remains regular if the target itself is regular. This regularity allows nested automata structures to perform exact verification across infinite state spaces. Similarly, Taolue Chen et al. utilized finite automata to recognize valid stack contents in Global Model Checking on Pushdown Multi-Agent Systems, enabling strategic verification across infinite configurations.
This encoding strategy is not limited to stacks; it applies to numbers as well. In Optimal Metric Planning with State Sets in Automata Representation, Björn Ulrich Borowsky et al. demonstrated that infinite sets of integers defined by linear logical constraints can be represented as deterministic finite automata. By reading the bit-string representations of numbers, the automaton can reason about infinite state spaces simultaneously in a single symbolic step, avoiding the precision loss of discretization.
Computing Reachability via Transducers and Fixed Points
To verify a system or find a plan, we must understand how states evolve over time. If sets of states are represented as languages, how do we model the transition relation?
The answer lies in finite-state transducers—automata that read an input string and output a modified string. In this framework, a transition is not an explicit edge between two states, but a regular relation between two words. Anthony Widjaja Lin et al. leveraged this in Algorithmic metatheorems for decidable LTL model checking over infinite systems, showing that modeling transitions via transducers allows formal language theory to unify verification proofs across diverse infinite-state systems like Petri nets and concurrent pushdown processes. This unified abstraction is powerful; Udi Boker et al. in History-Determinism vs Fair Simulation demonstrated how a generalized infinite-state abstraction can provide uniform proofs across distinct architectures like pushdown automata and vector addition systems.
Using these transducers, a verifier can perform symbolic backward reachability. Starting with an automaton representing a set of "bad" or target states, the verifier applies a predecessor operator to compute a new automaton representing all states that can transition into those bad states. By iteratively computing these predecessors, the system constructs a cascading fixed point.
To ensure this iterative search terminates over an infinite space, Parosh Aziz Abdulla et al. in Counter-Example Guided Fence Insertion under TSO combined specialized finite-state automata with the theory of well-quasi-ordered systems, guaranteeing that the search for error states always converges. For probabilistic and non-deterministic settings, Marta Z. Kwiatkowska et al. in Symbolic Computation of Maximal Probabilistic Reachability showed that representing infinite sets via symbolic zones or intervals allows for the exact computation of maximal reachability probabilities.
Evolving the Automaton: Predicates and Formulas
Standard automata operate over a finite alphabet of characters. However, real-world data often involves infinite alphabets, such as real numbers, database keys, or unbounded strings. To bridge this gap, researchers evolved the underlying automata models.
One major evolution is the symbolic finite automaton, introduced in this context by Loris D'Antoni et al. in Symbolic WS1S. Instead of labeling transitions with discrete characters, symbolic automata label transitions with predicates from a decidable theory (e.g., $x \in \mathbb{Z}, x > 4$). This allows a single symbolic transition to represent infinitely many concrete transitions.
Taking this a step further, Luca Geatti et al. introduced First-Order Automata, where the entire automaton—initial conditions, transitions, and acceptance criteria—is defined using first-order formulas rather than explicit state-transition graphs. This allows for a compact, finite description of systems with unbounded data types.
When dealing with complex data-aware processes, Alessandro Gianola et al. in Linear-Time Verification of Data-Aware Processes Modulo Theories via Covers and Automata combined automata theory with symbolic "covers" from Satisfiability Modulo Theories (SMT). These covers summarize infinite data spaces into the strongest quantifier-free formulas, allowing the verifier to discard irrelevant historical data while maintaining enough information to verify temporal properties.
Even when managing complex program analysis constraints, this mapping proves vital. John Kodumal in Regularly annotated set constraints showed that mapping regular language annotations to states within a finite state automaton bounds the complexity of constraint manipulation, providing a unified approach to type-based flow analysis.
Beyond Verification: Planning, Learning, and Optimization
While initially designed for formal verification, treating infinite state spaces as regular languages has unlocked breakthroughs in synthesis, optimization, and machine learning.
In reactive synthesis and game theory, Daniel Neider demonstrated in An Automaton Learning Approach to Solving Safety Games over Infinite Graphs that safety games over infinite graphs can be solved by representing vertex sets as regular languages and transitions as transducers. By framing the search for a winning region as an active automata learning problem, the author bypassed the need for exhaustive graph exploration.
In the realm of artificial intelligence, Taylor Dohmen et al. introduced Regular Reinforcement Learning. Traditional reinforcement learning relies on explicit state vectors, which struggle with infinite or structurally complex environments. By representing environment states as regular languages via finite state automata and transitions as rational transductions, the authors enabled RL agents to reason about sets of states defined by formal rules, allowing them to generalize across infinite state spaces.
Finally, for quantitative analysis, Krishnendu Chatterjee et al. in Faster Algorithms for Weighted Recursive State Machines utilized finite weighted automata to represent the potentially infinite set of reachable states in recursive systems. This serves as a compact symbolic data structure that decouples the initial reachability construction from subsequent distance queries, yielding massive algorithmic speedups.
Key Foundational Work
Symbolic Computation of Maximal Probabilistic Reachability (2001) — contributed 1 concept elements to this direction.
Equivalence Checking for Infinite Systems Using Parameterized Boolean Equation Systems (2007) — contributed 1 concept elements to this direction.
Regularly annotated set constraints (2007) — contributed 1 concept elements to this direction.