Séminaire Algorithmique « History-deterministic and explorable automata », Denis Kuperberg (LIP, ENS Lyon)

History-deterministic automata are intermediary between deterministic and nondeterministic ones, and have been the object of thorough study in the last decade. They offer a way to get a better grasp of the power of nondeterminism, by allowing only some aspects of it: nondeterministic choices are allowed to depend on the past of the computation but not on the future. I will present the state of the art on the understanding of these history-deterministic automata, as well as open problems related to complexity questions. If time permits, I will finish by presenting a recent generalization of history-determinism called explorable automata, where more nondeterminism is allowed, and some intriguing decidability questions remain open.