Do probabilities matter for resolving nondeterminism?
Consider a nondeterministic parity automaton where: is a finite set of states, is the input alphabet, is the transition relation, is the initial state, and is the parity acceptance condition. We say that a probabilistic automaton is obtained from a memoryless resolver for if, for each state and input symbol , the nondeterministic set of successors
is replaced by a probability distribution over that set. The resulting probabilistic automaton retains the same state set , alphabet , and initial state , but transitions are decided by the probability distributions which define the probability of moving from state to state upon reading symbol . We say that is memoryless stochastically resolvable if there exists a probabilistic automaton , obtained from a memoryless resolver as described above, such that for every infinite word accepted by , the probabilistic automaton also accepts with probability 1. Moreover, we say that is obtained from uniform memoryless resolver if, for all and , the distribution is uniform over the set This leads to the question: If a nondeterministic parity automaton is stochastically resolvable using a memoryless resolver, is it always possible to construct such a resolver using uniform distributions?
