Where can I find an introduction to probabilistic automata and what they recognize (certain functions from words to $[0,1]$)? Is there a standard term for such functions which are recognized by probabilistic automata, analogous to "regular languages" for what deterministic finite automata (DFAs) recognize?

I'm looking for something which approaches it analogously to studying basic questions on DFAs and regular languages, such as expressiveness, closure, and decidability properties.

This and this don't quite seem to be what I'm looking for.

  • $\begingroup$ They are the "positive supports" of $\mathbb{Z}$-rational series, i.e., the languages $\{w \mid (r, w) > 0\}$ for $r$ such a series. This is not all too well behaved, though. I studied the Boolean closure of this class, if you are interested: eccc.hpi-web.de/report/2013/040. $\endgroup$ Apr 29 '16 at 12:15

The first paper by Rabin (1963) gives the basics what you are looking for. The class of languages recognized by probabilistic automata (with cutpoint) is called stochastic languages.

Let $P$ be a probabilistic automaton defined on the alphabet $ \Sigma $ and $ f_P(w) $ be the accepting probability of $ P $ on the input $ w \in \Sigma^* $. Then, $P$ with cutpoint $\lambda \in [0,1)$ defines the following language:

$ L(P,\lambda) = \{ w \in \Sigma^* \mid f_P(w) > \lambda \} $.

Remark that the recognition with cutpoint can be seen as recognition with unbounded error. In case of bounded-error (or isolated cutpoint) probabilistic automata can recognize all and only regular languages.

The book by Paz (1971) and the survey by Bukharaev (1980) are good references.

You can also check a recent survey on quantum automata where you can trace some references on probabilistic automata.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.