Second, despite of the existing quadratic gap between Las Vegas realtime probabilistic automata and one-way deterministic automata for language recognition, we show that, by turning to promise problems, the tight gap becomes exponential.
Keywords: descriptional complexity, promise problems, nondeterministic automata, probabilistic automata, alternating automata
Among others, we show that (i) the computational power of deterministic, nondeterministic, alternating, and Las Vegas probabilistic automata is the same, even after turning from the classical language recognition to solving promise problems, and, (ii) on promise problems, neither existing gaps of succinctness for classical language recognition can be violated, between any two of deterministic, nondeterministic, and alternating automata models.
Finally, we prove that, on promise problems, bounded-error probabilistic automata are more powerful than any other classical model.
Links between probabilistic automata and hidden markov models: probability distributions, learning models and induction algorithms, Pattern Recognition, 38(2004), 1349-1371.
Henzinger, Probabilistic Automata on Infinite Words: Decidability and Undecidability Results, Springer-Verlag, 6252(2010), 1-16.
Introduction to Probabilistic Automata, Academic Press, New York, 1971.
More general models, such as the 2QCFA, employing mixed states, are able to simulate the corresponding classical probabilistic automata efficiently in both the one-way and two-way settings, and to recognize some languages that 2PFAs cannot [AW02].
Stochasticity of the languages acceptable by two-way finite probabilistic automata.
On languages representable in rational probabilistic automata.