# Epsilon-closure and DFA minimization algorithms for probabilistic NFA

Are there any algorithms performing e-closures and DFA minimizations for probabilistic Finite Automata? Given that probabilistic NFAs might have multiple accepting paths for generating equivalent strings with different probabilities, do current minimization algorithms allow to reduce such amount of complexity to generating just one string with given fixed probability?

I am aware of e-closure and DFA minimization for standard Finite Automata, but I was able to find no paper/algorithm for automata with probabilities.

• Can you specify exactly the model you refer to? Probabilistic transitions usually replace nondeterminism, not added to it (otherwise you need to give a quantitative semantics to nondeterminism). Also, state minimization would not change the probabilities of accepted strings (it shouldn't, anyway). May 27 at 18:00
• I'm thinking to the same definition as in en.wikipedia.org/wiki/Probabilistic_automaton, where Σ also contains ε and, given one source state and a label, there could be possibly many reachable states. We can also make some restriction to such automaton, so that it never contains paths accepting ε and there are no loops generating a ε substring, but I think that such assumptions are irrelevant with respect to the aforementioned algorithms. May 27 at 18:18
• p.s. What do you mean with "quantitative semantics to non-determinism"? Where can I find some additional references? May 27 at 18:20