# zbMATH — the first resource for mathematics

Probabilistic automata on finite words: decidable and undecidable problems. (English) Zbl 1288.68156
Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-14161-4/pbk). Lecture Notes in Computer Science 6199, 527-538 (2010).
Summary: This paper tackles 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 \leq \lambda \leq 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 and prove that it is undecidable for automata with as few as two probabilistic transitions. 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.
For the entire collection see [Zbl 1194.68006].

##### MSC:
 68Q45 Formal languages and automata 68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Full Text: