The value 1 problem for probabilistic automata

Prelegent(ci)

Nathanaël Fijalkow

Afiliacja

Uniwersytet Warszawski

Termin

19 marca 2014 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

I will talk about probabilistic automata, which are automata assigning to each word a probability to be accepted. Specifically, I will be interested in the value 1 problem, which asks whether for a given probabilistic automaton, there are words accepted with acceptance probability arbitrarily close to 1.

Although this problem is undecidable, I'll try to convince you that there are still many things to say about it.

When I first came in Warsaw I gave a seminar talk and introduced two objects: the Markov monoid algorithm and the leaktight property. The first is a saturation algorithm that (incompletely) solves the value 1 problem, and the second is a sufficient condition for probabilistic automata ensuring this algorithm to be correct.

This talk is a continuation of the previous one. I plan to discuss two attempts to answer the following question: "what does the Markov monoid algorithm compute?".

---