14:00
15:00

Aditya Prakash
Resolving nondeterminism in automata

In this talk, we will look at automata where nondeterminism can be resolved on-the-fly, such that this resolution constructs accepting runs on accepting words. The automata where this is possible are called history deterministic automata. We will look at the complexity and algorithms for the problem of recognising history-deterministic automata. We will also look at automata where the resolution of nondeterminism can be done by a stochastic policy. I will end the talk with my currently favourite conjecture on such automata, which, if true, would have an elegant implication for population games.

Français
178