Stochastization of Weighted Automata

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 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 stochastization of WFAs: given a WFA \(\mathcal{A}\), stochastization turns it into a PWFA \(\mathcal{A}'\) by labeling its transitions by probabilities. The weight of a word in \(\mathcal{A}'\) can only increase with respect to its weight in \(\mathcal{A}\), and we seek stochastizations in which \(\mathcal{A}'\) \(\alpha \)-approximates \(\mathcal{A}\) for the minimal possible factor \(\alpha \ge 1\). That is, the weight of every word in \(\mathcal{A}'\) is at most \(\alpha \) times its weight in \(\mathcal{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 \(\mathcal{A}\) and a factor \(\alpha \ge 1\), whether there is a stochastization of \(\mathcal{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.