Stochastization of Weighted Automata
====================================

{\em Nondeterministic weighted finite automata\/} (WFAs) map input words to real numbers. Each transition of a WFA is labeled by both a letter from some alphabet and a weight. The weight of a run is the sum of the weights on the transitions it traverses, and the weight of a word is the minimal weight of a  run on it. In {\em probabilistic weighted automata\/} (PWFAs), the transitions are further labeled by probabilities, and the weight of a word is the expected weight of a run on it. 

We define and study {\em stochastization} of WFAs: given a WFA $\A$, stochastization turns it into a PWFA $\A'$ by labeling its transitions by probabilities. The weight of a word in $\A'$ can only increase with respect to its weight in $\A$, and we seek stochastizations in which $\A'$ $\alpha$-approximates $\A$ for the minimal possible factor $\alpha \geq 1$. That is, the weight of every word in $\A'$ is at most $\alpha$ times its weight in $\A$. 

We show that stochastization is useful in reasoning about the competitive ratio of randomized online algorithms and in approximated determinization of WFAs. 

We study the problem of deciding, given a WFA $\A$ and a factor $\alpha \geq 1$, whether there is a stochastization of $\A$ that achieves an $\alpha$-approximation. We show that the problem is in general undecidable, yet can be solved in PSPACE for a useful class of WFAs.