Profinite Techniques for Probabilistic Automata

Abstract

The model of (reactive) probabilistic automata was introduced by Rabin
in 1963 [10], generalising non-deterministic automata by assigning probabilities
to transitions. Such an automaton associates with a word a value
between 0 and 1, which is the probability that the run is accepted.
This extended abstract presents recent progress on the value 1 problem
for probabilistic automata, which asks whether given a probabilistic automaton,
there exist words accepted with arbitrarily high probability.
Since its introduction by Gimbert and Oualhadj in 2010 [8], the value 1
problem has been studied at great depth, leading to the development of new
tools of algorithmic, algebraic, and topological nature. We report on a recent
paper which introduces a topological approach called the prostochastic
theory for understanding the value 1 problem [6, 7].