  Probabilistic automata are an extension of nondeterministic finite automata
in which transitions are annotated with probabilities. Despite its simplicity,
this model is very expressive and many of the associated algorithmic questions
are undecidable. In this work we focus on the emptiness problem (and its
variant the value problem), which asks whether a given probabilistic automaton
accepts some word with probability greater than a given threshold. We consider
a natural and well-studied structural restriction on automata, namely the
degree of ambiguity, which is defined as the maximum number of accepting runs
over all words. The known undecidability proofs exploits infinite ambiguity and
so we focus on the case of finitely ambiguous probabilistic automata. Our main
contributions are to construct efficient algorithms for analysing finitely
ambiguous probabilistic automata through a reduction to a multi-objective
optimisation problem called the stochastic path problem. We obtain a polynomial
time algorithm for approximating the value of probabilistic automata of fixed
ambiguity and a quasi-polynomial time algorithm for the emptiness problem for
2-ambiguous probabilistic automata. We complement these positive results by an
inapproximability result stating that the value of finitely ambiguous
probabilistic automata cannot be approximated unless PTIME = NP.
