Spring 2021

Fellows Talk

Mar 11, 2021 11:00 am – 12:00 pm 

Add to Calendar


Karoliina Lehtinen (University of Liverpool)



Title: Between Determinism and Nondeterminism, What are Good-For-Games Automata Good for?

Abstract: Nondeterminism probably makes your favourite automata model more expressive, or at least more succinct, than determinism. However, nondeterminism comes with higher algorithmic complexity. Good-for-games automata, also known as history deterministic automata, lie in between deterministic and nondeterministic models, trying to salvage some of the expressivity and succinctness of nondeterminism, without giving up on the nice algorithmic properties of deterministic automata.

In this talk, I will give an overview of good-for-games automata, survey recent developments in the area for regular, pushdown and maybe even timed automata, and point to some of the hard questions that remain unanswered and some areas that remain unexplored.