Resolving Nondeterminism by Chance
This addresses probabilistic verification problems for formal methods researchers, presenting both undecidability results and decidable subcases.
The paper tackles the problem of checking qualitative properties in probabilistic verification by studying automata where nondeterministic choices can be resolved with randomized strategies that succeed with bounded probability. The main result shows that determining if a given NFA is λ-stochastically resolvable is undecidable, though it's decidable for finitely-ambiguous automata, with complexity bounds provided for other decidable cases.
History-deterministic automata are those in which nondeterministic choices can be correctly resolved stepwise: there is a strategy to select a continuation of a run given the next input letter so that if the overall input word admits some accepting run, then the constructed run is also accepting. Motivated by checking qualitative properties in probabilistic verification, we consider the setting where the resolver strategy can randomize and only needs to succeed with lower-bounded probability. We study the expressiveness of such stochastically-resolvable automata as well as consider the decision questions of whether a given automaton has this property. In particular, we show that it is undecidable to check if a given NFA is $λ$-stochastically resolvable. This problem is decidable for finitely-ambiguous automata. We also present complexity upper and lower bounds for several well-studied classes of automata for which this problem remains decidable.