Deciding the Value 1 Problem of Probabilistic Leaktight Automata

Details Deciding the Value 1 Problem of Probabilistic Leaktight Automata Deciding the Value 1 Problem of Probabilistic Leaktight Automata

2011-04-14

arxiv.org/abs/1104.3055v5

Computer Science

Formal Languages and Automata Theory

arXiv admin note: significant text overlap with arXiv:1104.3054

Scientific paper

The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton A, are there words accepted by A with probability arbitrarily close to 1? This problem was proved undecidable recently. We sharpen this result, showing that the undecidability result holds even if the probabilistic automata have only one probabilistic transition. Our main contribution is to introduce a new class of probabilistic automata, called leaktight automata, for which the value 1 problem is shown decidable (and PSPACE-complete). We construct an algorithm based on the computation of a monoid abstracting the behaviours of the automaton, and rely on algebraic techniques developed by Simon for the correctness proof. The class of leaktight automata is decidable in PSPACE, subsumes all subclasses of probabilistic automata whose value 1 problem is known to be decidable (in particular deterministic automata), and is closed under two natural composition operators.

Affiliated with

Also associated with

No associations

Rating

Deciding the Value 1 Problem of Probabilistic Leaktight Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deciding the Value 1 Problem of Probabilistic Leaktight Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deciding the Value 1 Problem of Probabilistic Leaktight Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-167938