<p>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 <a href="http://perso.telecom-paristech.fr/~jsaka/ETA/eta-eng.html" rel="nofollow">Elements of Automata Theory</a> by Jacques Sakarovitch (also available in French): 
For shorter explanations, check out the <a href="http://perso.telecom-paristech.fr/~jsaka/ENSG/MPRI/mpri.html#CoursI" rel="nofollow">lecture notes</a> by Jacques Sakarovitch again: </p>

<p>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 <a href="http://perso.telecom-paristech.fr/~jsaka/ENSG/MPRI/Files/Lectures/FLAT-L3.pdf" rel="nofollow">lecture note</a>).</p>

CC BY-SA 3.0
2013-06-20T10:54:39.440Z
2013-06-20T10:54:39.440Z
Denis
<p>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.</p>

<p>See also a <a href="https://cs.stackexchange.com/q/12624/5323">related question</a>.</p>

<ul>
<li>Richard Mayr and Lorenzo Clemente, <em>Advanced automata minimization</em>, POPL 2013, doi:<a href="http://dx.doi.org/10.1145/2429069.2429079" rel="nofollow noreferrer">10.1145/2429069.2429079</a> (<a href="http://arxiv.org/abs/1210.6624" rel="nofollow noreferrer">preprint</a>)</li>
</ul>

CC BY-SA 3.0
2013-06-22T18:26:28.693Z
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?
hr0nix
CC BY-SA 3.0
2013-06-22T20:28:36.850Z
Doesn't the locality restriction help with that?
András Salamon
CC BY-SA 3.0
2013-06-22T20:49:44.360Z
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.
hr0nix
CC BY-SA 3.0
2013-06-22T21:20:41.167Z
Hmmm, you do have a point.  My intuition that this could be used may have been wrong.
András Salamon
CC BY-SA 3.0
2013-06-19T14:04:19.823Z
2013-06-19T14:04:19.823Z
2017-04-13T12:48:30.830Z
András Salamon
<p>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).</p>

<p>See <a href="http://www.cs.huji.ac.il/~ornak/publications/lics11a.pdf" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2013-06-19T15:06:44.987Z
This algorithm is over the tropical semiring, not the probabilistic. Making the transition is not certain to be simple, or even possible.
Shaull
CC BY-SA 3.0
2013-06-19T17:30:31.340Z
Also, what about the concern that minimal DFA can have more states than the original NFA because of the exponential state space explosion?
hr0nix
CC BY-SA 3.0
2013-06-23T08:22:59.917Z
@Shaull is ofcourse correct, I missed that.
Shir
CC BY-SA 3.0
2013-06-23T08:25:35.290Z
@hr0nix, "reduce the complexity of an NFA" is not well defined. In my opinion determinization is simplification of sort.
Shir
CC BY-SA 3.0
2013-06-23T11:53:42.867Z
@Shir, in the question I define simplification as a reduction of the number of states.
hr0nix
CC BY-SA 3.0
2013-06-19T11:12:17.487Z
2013-06-19T11:12:17.487Z
Shir
<p>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</p>

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

<p>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?</p>

<fl.formal-languages><automata-theory><heuristics><probabilistic-automata>
Simplification of weighted NFA
hr0nix
# Simplification of weighted NFA

(Asked by: username_0 on 2013-06-19)

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?

**Tags:** fl.formal-languages, automata-theory, heuristics, probabilistic-automata


---

## 3 answers

### Answer by username_1 on 2013-06-20. Score: 3

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](http://perso.telecom-paristech.fr/~jsaka/ETA/eta-eng.html) by Jacques Sakarovitch (also available in French):
For shorter explanations, check out the [lecture notes](http://perso.telecom-paristech.fr/~jsaka/ENSG/MPRI/mpri.html#CoursI) 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](http://perso.telecom-paristech.fr/~jsaka/ENSG/MPRI/Files/Lectures/FLAT-L3.pdf)).


---

### Answer by username_2 on 2013-06-19. Score: 2

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](https://cs.stackexchange.com/q/12624/5323).

* Richard Mayr and Lorenzo Clemente, *Advanced automata minimization*, POPL 2013, doi:[10.1145/2429069.2429079](http://dx.doi.org/10.1145/2429069.2429079) ([preprint](http://arxiv.org/abs/1210.6624))

> **Comments:**
> **username_0**: 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?  
> **username_2**: Doesn't the locality restriction help with that?  
> **username_0**: 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.  
> **username_2**: Hmmm, you do have a point.  My intuition that this could be used may have been wrong.  

---

### Answer by username_3 on 2013-06-19. Score: 1

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](http://www.cs.huji.ac.il/~ornak/publications/lics11a.pdf).

> **Comments:**
> **username_4**: This algorithm is over the tropical semiring, not the probabilistic. Making the transition is not certain to be simple, or even possible.  
> **username_0**: Also, what about the concern that minimal DFA can have more states than the original NFA because of the exponential state space explosion?  
> **username_3**: @username_4 is ofcourse correct, I missed that.  
> **username_3**: @username_0, "reduce the complexity of an NFA" is not well defined. In my opinion determinization is simplification of sort.  
> **username_0**: @username_3, in the question I define simplification as a reduction of the number of states.  

---

