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?