The value 1 problem for probabilistic automata

Speaker(s)

Nathanaël Fijalkow

Affiliation

Uniwersytet Warszawski

Date

March 19, 2014, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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?".

---