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].

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