On Higher-Order Reachability Games vs May Reachability

Kazuyuki Asada, Hiroyuki Katsura, Naoki Kobayashi

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:

  1. 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.
  2. 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

Abstract

We consider the reachability problem for higher-order functional programs and study the relationship between reachability games (i.e., the reachability problem for programs with angelic and demonic nondeterminism) and may-reachability (i.e., the reachability problem for programs with only angelic nondeterminism). We show that reachability games for order-n programs can be reduced to may-reachability for order-(n+1) programs, and vice versa. We formalize the reductions by using higher-order fixpoint logic and prove their correctness. We also discuss applications of the reductions to higher-order program verification.
BibTeX
@inproceedings{asada2022higher,
  author = {Kazuyuki Asada and Hiroyuki Katsura and Naoki Kobayashi},
  title = {{On Higher-Order Reachability Games vs May Reachability}},
  booktitle = {RP},
  year = {2022},
  url = {https://openreview.net/forum?id=kVi95KjFVd},
}
Figure