← All problems
Unverified

Do probabilities matter for resolving nondeterminism?

Consider a nondeterministic parity automaton A=(Q,Σ,Δ,q0,Ω),A = (Q, \Sigma, \Delta, q_0, \Omega), where: QQ is a finite set of states, Σ\Sigma is the input alphabet, Δ⊆Q×Σ×Q\Delta \subseteq Q \times \Sigma \times Q is the transition relation, q0∈Qq_0 \in Q is the initial state, and Ω:Q→N\Omega : Q \to \mathbb{N} is the parity acceptance condition. We say that a probabilistic automaton PP is obtained from a memoryless resolver for AA if, for each state s∈Qs \in Q and input symbol a∈Σa \in \Sigma, the nondeterministic set of successors

{t∈Q∣(s,a,t)∈Δ}\{ t \in Q \mid (s, a, t) \in \Delta \}

is replaced by a probability distribution DsaD_s^a over that set. The resulting probabilistic automaton PP retains the same state set QQ, alphabet Σ\Sigma, and initial state q0q_0, but transitions are decided by the probability distributions {Dsa}s∈Q,a∈Σ,\{ D_s^a \}_{s \in Q, a \in \Sigma}, which define the probability of moving from state ss to state tt upon reading symbol aa. We say that AA is memoryless stochastically resolvable if there exists a probabilistic automaton PP, obtained from a memoryless resolver as described above, such that for every infinite word w∈Σωw \in \Sigma^\omega accepted by AA, the probabilistic automaton PP also accepts ww with probability 1. Moreover, we say that PP is obtained from uniform memoryless resolver if, for all s∈Qs \in Q and a∈Σa \in \Sigma, the distribution DsaD_s^a is uniform over the set {t∈Q∣(s,a,t)∈Δ}.\{ t \in Q \mid (s, a, t) \in \Delta \}. This leads to the question: If a nondeterministic parity automaton AA is stochastically resolvable using a memoryless resolver, is it always possible to construct such a resolver using uniform distributions?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu