Abstract
This paper establishes a fundamental computational equivalence between two-player reachability games of order $n$ and one-player "may-reachability" problems of order $n+1$. By utilizing $\mu$HFL(Z)—a fragment of higher-order fixpoint logic—as a bridging formalism, the authors demonstrate that the complexity of demonic nondeterminism in games can be traded for higher-order abstraction in programs. This theoretical insight is supported by polynomial-time, size-preserving translations that enable tool interoperability and yield significant performance improvements on existing verification benchmarks.
Introduction
In the field of formal verification, determining whether a program can reach a specific state—such as an error condition or a successful termination point—is a central challenge. This problem is typically framed in one of two ways:
- May-Reachability: A "one-player" scenario where the goal is to determine if there exists any sequence of non-deterministic choices that leads to the target state. This is the standard model for safety checking.
- Reachability Games: A "two-player" scenario involving "angelic" choices (made by the player to reach the goal) and "demonic" choices (made by an opponent or the environment to prevent it). This model is essential for verifying properties like termination under all possible environmental behaviors.
As programs utilize higher-order functions (functions that accept other functions as arguments), these problems become increasingly complex. While specialized tools exist for both paradigms, the relationship between them in a higher-order context has remained under-explored. This paper addresses this gap by proving that these two classes of problems are, in fact, different expressions of the same underlying complexity.
Theoretical Framework: $\mu$HFL(Z)
To bridge the gap between program syntax and game theory, the authors employ $\mu$HFL(Z), a fragment of higher-order fixpoint logic with integers. This logic is particularly suited for this task because there is a direct correspondence between program reachability and the validity of $\mu$HFL(Z) formulas. In this logic, angelic choices map to disjunctions, while demonic choices map to conjunctions. This formalization allows the authors to treat the problem as a logical transformation rather than a purely syntactic one.
The Order-Shift Trade-off
The core contribution of the paper is the definition of two polynomial-time, size-preserving translations:
1. Order-$n$ Game to Order-$(n+1)$ May-Reachability
The authors show that the "demonic" choices in an order-$n$ game can be simulated by a one-player program of order $n+1$. In this translation, the demonic requirements are transformed into higher-order function arguments. Essentially, the one-player program uses these higher-order structures to "track" the constraints that an opponent would have imposed in a game setting. This reveals that demonic nondeterminism is not inherently more complex than angelic nondeterminism; it simply requires a higher level of abstraction to represent as a single-player problem.
2. Order-$(n+1)$ May-Reachability to Order-$n$ Game
Conversely, the authors prove that the extra "order" of a program can be traded back for the complexity of a two-player game. This reverse translation demonstrates that the relationship is a true equivalence, allowing researchers to move fluidly between these two problem classes depending on which is more convenient for a given solver.
Experimental Results
The practical utility of these translations was evaluated using the RETHFL benchmark suite, which focuses on non-termination problems. By applying the translation to create RETHFL+tr., the authors tested whether shifting the problem type could improve solver efficiency.
The results indicated substantial performance gains on several complex benchmarks:
unfoldr_nonterm: The standard solver timed out after 180 seconds, whereas the translated version reached a solution in 4.22 seconds.loopHO: This test also moved from a timeout to a completion time of just 0.121 seconds.
These results suggest that while the translations are theoretically size-preserving, they can significantly alter the search space in ways that favor existing automated solvers.
Discussion and Limitations
While the theoretical equivalence is robust, the authors note that practical performance is highly dependent on solver sensitivity. Although the translation simplifies the type of nondeterminism (moving from two-player to one-player), it increases the type order of the program. Some verification tools are highly sensitive to increased type orders, which may, in some cases, make the translated problem more difficult for specific algorithms to solve.
Furthermore, this work focuses on $\mu$HFL(Z), which is restricted to least fixpoints. Extending these translations to full HFL(Z)—which includes greatest fixpoints for liveness properties—remains a complex objective for future research. The implications for other infinite data domains beyond integers also remain to be fully explored.
Conclusion
By establishing that order-$n$ reachability games and order-$(n+1)$ may-reachability are effectively the same problem class, this paper provides a new lens through which to view higher-order verification. The ability to translate between these paradigms allows for greater tool interoperability, enabling safety-checking tools to solve game-theoretic problems and vice versa. This "order-shift" insight provides a powerful new strategy for tackling the inherent complexity of higher-order functional programs.
Summary updated