13:00
14:00

A nondeterministic parity automaton is history-deterministic if there is a resolver that can resolve the nondeterminism on the fly while reading a word, based on the prefix read so far. The notion of history-determinism has been studied extensively over the recent years, yet the complexity of deciding history-determinism for parity automata has remained open since 2006.

In this talk, I will present some recent progress we have made on this problem. This is based on part published and part ongoing works, together with Rohan Acharya, Marcin Jurdziński, and Karoliina Lehtinen.

076