<p>Stefan Kiefer has some work on minimization of probabilistic automata. This should probably put you on the right track:
<a href="https://arxiv.org/abs/1404.6673" rel="nofollow noreferrer">https://arxiv.org/abs/1404.6673</a>.</p>

CC BY-SA 4.0
2021-05-28T11:07:05.927Z
Thanks, are there peer-reviewed and recent papers on the topic that you might suggest, perhaphs by the same authors?
jackb
CC BY-SA 4.0
2021-05-28T11:52:42.560Z
The paper in the answer was peer-reviewed, and published in ICALP 2014.
Shaull
CC BY-SA 4.0
2021-05-27T18:24:21.133Z
2021-05-27T18:24:21.133Z
Shaull
<p>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?</p>
<p>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.</p>

CC BY-SA 4.0
2021-05-27T18:00:22.267Z
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).
Shaull
CC BY-SA 4.0
2021-05-27T18:18:12.983Z
I'm thinking to the same definition as in https://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.
jackb
CC BY-SA 4.0
2021-05-27T18:20:16.367Z
p.s. What do you mean with "quantitative semantics to non-determinism"? Where can I find some additional references?
jackb
<minimization><probabilistic-automata>
Epsilon-closure and DFA minimization algorithms for probabilistic NFA
jackb
# Epsilon-closure and DFA minimization algorithms for probabilistic NFA

(Asked by: username_0 on 2021-05-27)

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.

**Tags:** minimization, probabilistic-automata

> **Comments:**
> **username_1**: 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).  
> **username_0**: I'm thinking to the same definition as in https://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.  
> **username_0**: p.s. What do you mean with "quantitative semantics to non-determinism"? Where can I find some additional references?  

---

## 1 answers

### Answer by username_1 on 2021-05-27. Score: 2 | Accepted answer

Stefan Kiefer has some work on minimization of probabilistic automata. This should probably put you on the right track:
<https://arxiv.org/abs/1404.6673>.

> **Comments:**
> **username_0**: Thanks, are there peer-reviewed and recent papers on the topic that you might suggest, perhaphs by the same authors?  
> **username_1**: The paper in the answer was peer-reviewed, and published in ICALP 2014.  

---

