### 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].

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].

#### Full Text:

PDF### Refbacks

- There are currently no refbacks.