Probabilistic Automata

Probabilistic automata were introduced by Rabin in 1963 as an automatic way to map input words with probabilities. They can be viewed as classic non deterministic finite automata, where transitions are labelled with a probability to be taken, given a state and a letter, and words have then a certain probability to be accepted. Probabilistic automata can be seen as a particular case of partially observable Markov decision processes and the natural problems that arise ask whether one can find input words with high probability to be accepted. This tutorial will introduce this model and we will discuss in particular some famous problems related to it, such as emptiness, value 1, approximation, equivalence and containment.

Authors

• Laure Daviaud

Keywords

No keywords are indexed for this paper.