Simplification of weighted NFA 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?
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).