History-Determinism vs Fair Simulation

Udi Boker, Thomas A. Henzinger, Karoliina Lehtinen, Aditya Prakash

Introduction

In the field of formal verification, the fundamental task is often to verify whether a system $A$ satisfies a specification $B$. This is typically modeled as a language inclusion problem: $L(A) \subseteq L(B)$. For nondeterministic automata, however, checking language inclusion is computationally expensive—often PSPACE-hard or even undecidable for infinite-state systems.

To circumvent this complexity, researchers frequently use fair simulation as a proxy. Simulation is a game-based approach that is significantly easier to compute than language inclusion. While simulation implies language inclusion, the reverse is not generally true. Automata for which these two notions coincide—where language inclusion is equivalent to simulation—are called guidable.

Another important concept is history-determinism (HD). An automaton is history-deterministic if its nondeterministic choices can be resolved "on the fly," based solely on the prefix of the word read so far, without knowledge of the future. While it is well-established that all HD automata are guidable, the converse has remained an open question. This paper investigates the "coincidence problem": under what conditions are guidability and history-determinism equivalent?

Theoretical Framework: Sufficient Criteria for Coincidence

The authors establish a robust framework to identify when history-determinism and guidability coincide. They propose three sufficient criteria (Theorem 1) that guarantee this equivalence for a given class of automata $C$:

  1. Determinisation: The class $C$ is such that every automaton has an equivalent deterministic or history-deterministic counterpart within the same class.
  2. 1-token Ghost: This criterion utilizes a "token game" variation. If a class is closed under a "1-token ghost"—a construction that creates a language-equivalent automaton but forces the player to resolve nondeterminism with a one-step delay—then guidability necessarily implies history-determinism.
  3. Strategy Ghost: This involves transforming the winning strategy of a "spoiler" (an opponent in a simulation game) into a specific type of automaton within the class that is inherently difficult to simulate.

These criteria allow for a systematic analysis of various automata classes, ranging from finite-state $\omega$-regular systems to complex infinite-state models.

Scope of Analysis: Infinite-State and Timed Systems

The study applies these criteria to a broad range of models, including Uniform Infinite State Systems. This generalized category encompasses several critical models in computer science:

  • Vector Addition Systems with States (VASS)
  • Pushdown Automata
  • One-counter Nets
  • Parikh Automata

Additionally, the authors examine Timed Automata (specifically those with safety and reachability conditions) and Visibly Pushdown Automata (VPA).

Key Insights: The Role of Resource Constraints

One of the paper's most significant findings is that the equivalence between history-determinism and guidability is often sensitive to resource limitations. The authors demonstrate that while the notions coincide for general classes, they diverge when constraints are placed on the "power" of the automaton.

For instance, in Büchi automata with a fixed, bounded number of states, or timed automata with a fixed number of clocks, it is possible to construct an automaton that is guidable but not history-deterministic. This suggests that history-determinism is a more "resource-heavy" property than guidability in these restricted settings.

Results and Practical Implications

The research provides a comprehensive taxonomy of the relationship between these two properties:

  • Coincidence (HD = Guidability): Confirmed for $\omega$-regular automata, VASS, pushdown automata, one-counter nets, Parikh automata, and timed automata with safety/reachability conditions.
  • Divergence (HD $\neq$ Guidability): Observed in resource-constrained environments, such as Büchi automata with bounded states and timed automata with a fixed number of clocks.

A major practical corollary of this work concerns decidability. Because the notions coincide for many complex classes, the problem of deciding guidability—which is often quite difficult—can be reduced to deciding history-determinism. This makes guidability decidable for classes like VPA and safety timed automata, typically with EXPTIME complexity.

Conclusion and Future Directions

While this paper clarifies the relationship between history-determinism and fair simulation for many standard models, several avenues for future research remain. The coincidence of these notions for pushdown and timed automata under general $\omega$-regular acceptance conditions (such as parity conditions) is still an open question. Furthermore, extending this framework to finite words and quantitative automata—where transitions involve weights or costs—presents a significant challenge, as the gap between letter-based games and simulation games typically widens in those contexts.

Summary updated

Abstract

An automaton is history-deterministic if its nondeterminism can be resolved on the fly, only using the prefix of the word read so far. This mild form of nondeterminism has attracted particular attention for its applications in synthesis problems. An automaton $A$ is guidable with respect to a class $C$ of automata if it can fairly simulate every automaton in $C$ whose language is contained in that of $A$. In other words, guidable automata are those for which inclusion and simulation coincide, making them particularly interesting for model-checking. We study the connection between these two notions, and specifically the question of when they coincide. For classes of automata on which they do, deciding guidability, an otherwise challenging decision problem, reduces to deciding history-determinism, a problem that is starting to be well-understood for many classes. We provide a selection of sufficient criteria for a class of automata to guarantee the coincidence of the notions, and use them to show that the notions coincide for the most common automata classes, among which are $\omega$-regular automata and many infinite-state automata with safety and reachability acceptance conditions, including vector addition systems with states, one-counter nets, pushdown-, Parikh-, and timed-automata. We also demonstrate that history-determinism and guidability do not always coincide, for example, for the classes of timed automata with a fixed number of clocks.
BibTeX
@inproceedings{boker2024history,
  author = {Udi Boker and Thomas A. Henzinger and Karoliina Lehtinen and Aditya Prakash},
  title = {{History-Determinism vs Fair Simulation}},
  booktitle = {CONCUR},
  year = {2024},
  url = {https://openreview.net/forum?id=JIJjW4bMHJ},
}
Figure