| Résumé |
We study three algorithmic problems for probabilistic automata on finite words: the Emptiness Problem, the Isolation Problem and the Value 1 Problem.
The Emptiness Problem asks, given some probability 0<=lambda<= 1, whether there exists a word accepted with probability greater than lambda, and the Isolation Problem asks whether there exist words whose acceptance probability is arbitrarily close to lambda. Both these problems are known to be undecidable.
About the Emptiness problem, we provide a new simple undecidability proof. The Value 1 Problem is the special case of the Isolation Problem when lambda=1 or lambda=0. The decidability of the Value 1 Problem was an open question. We show that the Value 1 Problem is undecidable. Moreover, we introduce a new class of probabilistic automata, #-acyclic automata, for which the Value 1 Problem is decidable.
|