Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata

Rohan Acharya, Marcin Jurdziński, Keya Prakash

Our main technical contribution is a polynomial-time determinisation procedure for history-deterministic Büchi automata, which settles an open question of Kuperberg and Skrzypczak,…