LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.


Between determinism and nondeterminism, what are good-for-games automata really good for?

13.10.2020, 11:00
Karoliina Lethinen (University of Liverpool)

Nondeterminism probably makes your favourite automata model more expressive, or at least more succint, than determinism. The downside is that nondeterminsism comes with higher algorithmic complexity. Good-for-games automata, also known as history deterministic automata, lie in between, 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, and point to some of the hard questions that remain unanswered.

About LSV