Paper Info
Title
Probabilistic automata on finite words: decidable and undecidable problems
Abstract
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 ≤ λ ≤ 1, whether there exists a word accepted with probability greater than λ, and the Isolation Problem asks whether there exist words whose acceptance probability is arbitrarily close to λ. Both these problems are known to be undecidable [11, 4, 3]. 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 λ = 1 or λ = 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.
Year
DOI
Venue
2010
10.1007/978-3-642-14162-1_44
ICALP (2)
Keywords
Field
DocType
emptiness problem,new simple undecidability proof,undecidable problem,finite word,acceptance probability,isolation problem,acyclic automaton,new class,probabilistic transition,algorithmic problem,probabilistic automaton,probabilistic automata
Post correspondence problem,Discrete mathematics,Quantum finite automata,Combinatorics,Decision problem,Word problem (mathematics),Existential quantification,Decidability,Mathematics,Probabilistic automaton,Undecidable problem
Conference
Volume
ISSN
ISBN
6199
0302-9743
3-642-14161-7
Citations 
PageRank 
References 
41
1.68
10
Authors
2
Name
Order
Citations
PageRank
Hugo Gimbert124921.31
Youssouf Oualhadj2606.99