We are happy to present Aditya Prakash’s talk titled “Recognising history-deterministic parity automata”.
A nondeterministic parity automaton is history-deterministic if there is a resolver that can resolve the nondeterminism while reading a word, based on the prefix read so far. The complexity of deciding history-determinism for parity automata is a problem that has remained open since 2006 and was only known to be in PTIME for Büchi and coBüchi automata till recently. I will present some recent progress we have made on this problem where we extended the PTIME decidability procedure to parity automata with 4 priorities.
This is based on joint work with Karoliina Lehtinen.
Aditya is a fourth-year PhD student at the University of Warwick, where he is working with Marcin Jurdzinski on automata and games, especially those on infinite words. During his PhD, his research has been focused on history-determinism, particularly on parity automata.