  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.
