You are not logged in |
Hopefully) the last talk about the value 1 problem for probabilistic automat
- Speaker(s)
- Nathanaël Fijalkow
- Affiliation
- Uniwersytet Warszawski
- Date
- Nov. 26, 2014, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
Since I started my PhD, I already spoke twice at this seminar about the value 1 problem for probabilistic automata. This talk shall be the last on this topic, as it hopefully answers the initial question: "what is computable about the value 1 problem?".
The first time, I explained that the value 1 problem is undecidable, that we have an algorithm, called the Markov Monoid Algorithm (MMA), and a subclass of probabilistic automata, the leaktight automata, such that
the MMA correctly solves the value 1 problem for leaktight automata.
The second time, I explained that relaxing the value 1 problem by abstracting away the numerical values does not lead to decidability.
This time, I will formalize the following claim: "the MMA is optimal". Inspired by Szymon Toruńczyk's PhD thesis, I will develop a theory of prostochastic words borrowing ideas from the profinite approach in automata theory. This new formulation allows for a simple characterization of the MMA, as well as a new undecidability result that shows that undecidability is around the corner, supporting the claim that the MMA is optimal.
The first time, I explained that the value 1 problem is undecidable, that we have an algorithm, called the Markov Monoid Algorithm (MMA), and a subclass of probabilistic automata, the leaktight automata, such that
the MMA correctly solves the value 1 problem for leaktight automata.
The second time, I explained that relaxing the value 1 problem by abstracting away the numerical values does not lead to decidability.
This time, I will formalize the following claim: "the MMA is optimal". Inspired by Szymon Toruńczyk's PhD thesis, I will develop a theory of prostochastic words borrowing ideas from the profinite approach in automata theory. This new formulation allows for a simple characterization of the MMA, as well as a new undecidability result that shows that undecidability is around the corner, supporting the claim that the MMA is optimal.
