6
$\begingroup$

What options does one have for the simplification (meaning reduction in the number of states) of weighted NFA over the probability semiring? From my understanding one can determinize, and then minimize an automaton, but

  • The minimal DFA can actually have more states than the original NFA
  • Not every weighted NFA is determinizable (in fact, most of them aren't)

My aim, however, is not necessarily to minimize an automaton, but simply reduce its complexity. So, what I'm looking for is a simplification algorithm that works directly with NFA and, while it doesn't guarantee to find the optimal solution, can simplify the automata in some cases significantly, and, presumably, has time complexity polynomial in the number of states. Are there any such algorithms known in literature?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

By simplification I understand either minimization or determinization. I'll try to sum up what I know about both problems, in the quite general setting of weighted automata over arbitrary semiring. The original works were done by Marcel-Paul Schützenberger (who introduced them), and you'll find a nice account of what is known about them in the book Elements of Automata Theory by Jacques Sakarovitch (also available in French): For shorter explanations, check out the lecture notes by Jacques Sakarovitch again:

For both minimization and determinization (called "sequentialization") there are nice theoretical answers. For instance, every weighted automaton over a field can be minimized in polynomial time (see for instance this lecture note).

Improve this answer
$\endgroup$
2
$\begingroup$

Mayr and Clemente have shown that it is often possible to simplify NFAs. Their techniques rely on pruning the underlying labelled transition system via local approximations of trace inclusions. As far as I can tell, this technique would still apply in the weighted case.

See also a related question.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the link, I wasn't aware of simplification techniques based on simulation relations. However, it's not immediately obvious to be how can one extend the concept of simulation game to the weighted case. The problem is that it's hard for Spoiler to prove that her state can't be simulated if the accepted languages induced by both her and Duplicator's states are the same and only weights are different, because in order to show that she has to aggregate weights for some word along all the accepting paths. Do you have any idea on how to fix that? $\endgroup$
    – hr0nix
    Commented Jun 22, 2013 at 18:26
  • $\begingroup$ Doesn't the locality restriction help with that? $\endgroup$
    – András Salamon
    Commented Jun 22, 2013 at 20:28
  • $\begingroup$ If by the locality restriction you mean small lookahead, then it doesn't seem to help. The problem as I see it is that even trace inclusions aren't sufficient in weighted case, not to speak about their local approximations. And the reason is that in the non-weighted case Spoiler can prove her point with a single trace, while in weighted case she needs all the traces since weights have to be aggregated. $\endgroup$
    – hr0nix
    Commented Jun 22, 2013 at 20:49
  • 1
    $\begingroup$ Hmmm, you do have a point. My intuition that this could be used may have been wrong. $\endgroup$
    – András Salamon
    Commented Jun 22, 2013 at 21:20
1
$\begingroup$

Actually there is an algorithm for approximated determinization of a weighted NFA, by Aminoff Kupferman and Lampert, where the approximation factor can be determined beforehand (if I remember correctly).

See here.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This algorithm is over the tropical semiring, not the probabilistic. Making the transition is not certain to be simple, or even possible. $\endgroup$
    – Shaull
    Commented Jun 19, 2013 at 15:06
  • $\begingroup$ Also, what about the concern that minimal DFA can have more states than the original NFA because of the exponential state space explosion? $\endgroup$
    – hr0nix
    Commented Jun 19, 2013 at 17:30
  • $\begingroup$ @Shaull is ofcourse correct, I missed that. $\endgroup$
    – Shir
    Commented Jun 23, 2013 at 8:22
  • $\begingroup$ @hr0nix, "reduce the complexity of an NFA" is not well defined. In my opinion determinization is simplification of sort. $\endgroup$
    – Shir
    Commented Jun 23, 2013 at 8:25
  • 1
    $\begingroup$ @Shir, in the question I define simplification as a reduction of the number of states. $\endgroup$
    – hr0nix
    Commented Jun 23, 2013 at 11:53

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.