Prelegent(ci)

Nathanaël Fijalkow

Afiliacja

Uniwersytet Warszawski

Termin

26 listopada 2014 14:15

Pokój

p. 5870

Tytuł w języku angielskim

Hopefully) the last talk about the value 1 problem for probabilistic automat

Seminarium

Seminarium „Teoria automatów”

---

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.

---