TL;DR
In formal verification, checking language inclusion is computationally expensive, whereas checking fair simulation is often efficient; automata where the two coincide are called guidable. This paper investigates when guidability is equivalent to history-determinism (the ability to resolve nondeterminism on the fly). The authors establish general criteria showing that these notions coincide for most standard finite- and infinite-state automata—enabling efficient algorithms for guidability—while showing they diverge when computational resources like states or clocks are bounded.
What Problem Does This Paper Address?
Model checking often boils down to a language inclusion query: does every execution of an implementation automaton $\mathcal{A}_{\text{sys}}$ satisfy a specification automaton $\mathcal{A}_{\text{spec}}$ ($L(\mathcal{A}_{\text{sys}}) \subseteq L(\mathcal{A}_{\text{spec}})$)? For nondeterministic automata over infinite words, language inclusion is notoriously hard (typically $\text{PSPACE}$-hard or undecidable).
Fair simulation is an alternative local game where a "duplicator" matches the transitions of a "spoiler." Simulation implies language inclusion and is much cheaper to check (often in polynomial time), but it is generally incomplete. Automata for which language inclusion and simulation coincide are termed guidable.
A related concept is history-determinism (HD) (or "good-for-games"): nondeterministic automata where choices can be made step-by-step based solely on the prefix read so far, without knowing the future. While HD automata are always guidable, whether all guidable automata are HD remained an open question. Deciding guidability directly is difficult because it quantifies over an infinite class of candidate automata. If guidability coincides with history-determinism, determining guidability reduces to checking HD, which is well-studied and algorithmically tractable.
Methods
The paper develops three sufficient criteria to prove that history-determinism and guidability coincide on an automaton class $\mathcal{C}$:
- Closure under (History-)Determinism: If every nondeterministic automaton in $\mathcal{C}$ has an equivalent deterministic (or HD) counterpart in $\mathcal{C}$.
- 1-Token Ghost Closure: Extending token games (where the spoiler Adam picks letters, the duplicator Eve chooses transitions in one automaton, and then Adam chooses transitions in another). An automaton $\mathcal{A}'$ is a 1-token ghost of $\mathcal{A}$ if $\mathcal{A}' \equiv \mathcal{A}$ and Eve wins the 1-token game between $\mathcal{A}'$ and $\mathcal{A}$. If 1-token games characterize HD in $\mathcal{C}$, and $\mathcal{A}' \in \mathcal{C}$ can always be constructed (often via a 1-step "delay" construction), then HD and guidability coincide.
- Strategy Ghost: For classes not closed under determinization or 1-token ghosts (like linear Büchi automata), the authors turn Adam’s winning strategy in the HD letter game into a deterministic automaton, project it onto the alphabet, and take its 1-token ghost. If that ghost stays within $\mathcal{C}$, guidability implies HD.
Datasets
Not applicable. This is a theoretical paper in formal automata theory and contains no empirical datasets.
Key Insights and Ideas
- Hard-to-simulate witnesses: Guidability requires an automaton $\mathcal{A}$ to simulate every language-included system. To prove non-HD implies non-guidability, one needs to identify a specific, language-included automaton $\mathcal{A}' \in \mathcal{C}$ that is "too difficult" for a non-HD automaton to simulate.
- The "Delay" mechanism: For many infinite-state systems (e.g., pushdown, VASS, counter nets), a 1-token ghost can be constructed generically by buffering the previous input letter in the finite-state control, letting the transition relation lag by one step.
- Resource bounds break equivalence: When an automaton class is artificially constrained by bounded resources (e.g., at most $k$ clocks or $2n$ states), guidability and history-determinism decouple. An automaton can be guidable simply because the class lacks the resource capacity to express the "hard" adversarial automaton that would expose non-history-determinism.
Key Results
- Equivalence across standard classes: History-determinism and guidability coincide for:
- Full $\omega$-regular automata, weak automata, and fixed-index parity automata (e.g., Büchi, co-Büchi).
- Visibly pushdown automata (VPAs) with any $\omega$-regular acceptance condition.
- Linear (very weak) Büchi automata.
- Infinite-state systems with safety and reachability acceptance, including Pushdown Automata (PDA), Vector Addition Systems with States (VASS), One-Counter Automata/Nets (OCA/OCN), and Parikh automata.
- Timed automata with safety or reachability acceptance.
- Complexity Corollaries: Guidability becomes decidable with the exact complexity of deciding history-determinism:
- $\text{PTIME}$ for Büchi and co-Büchi automata.
- $\text{EXPTIME}$ for parity automata, safety/reachability timed automata, and visibly pushdown automata.
- Separation Counterexamples:
- For any $n \ge 1$, Büchi automata with at most $2n$ states admit guidable automata that are not HD.
- For any $k \ge 0$, timed automata with at most $k$ clocks admit guidable automata that are not HD.
Limitations and Future Work
- General $\omega$-regular infinite-state systems: The question of whether HD equals guidability remains open for pushdown, one-counter, and timed automata equipped with general $\omega$-regular (e.g., Büchi or parity) conditions.
- Domain extensions: The proofs in this paper target infinite words ($\omega$-words). The authors suggest that adapting the techniques to finite words, register automata, and quantitative/weighted automata are natural next steps.
Summary updated