0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – Shaull
    Commented May 27, 2021 at 18:00
  • $\begingroup$ 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. $\endgroup$
    – jackb
    Commented May 27, 2021 at 18:18
  • $\begingroup$ p.s. What do you mean with "quantitative semantics to non-determinism"? Where can I find some additional references? $\endgroup$
    – jackb
    Commented May 27, 2021 at 18:20

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, are there peer-reviewed and recent papers on the topic that you might suggest, perhaphs by the same authors? $\endgroup$
    – jackb
    Commented May 28, 2021 at 11:07
  • 1
    $\begingroup$ The paper in the answer was peer-reviewed, and published in ICALP 2014. $\endgroup$
    – Shaull
    Commented May 28, 2021 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.