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

Title in Polish

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.

---