Chargement Évènements

« Tous les Évènements

  • Cet évènement est passé

Séminaire Algorithmique « Synthesis for fragments of first-order logic on data words », Denis Kuperberg (LIP, ENS Lyon)

14 mai / 10:00 - 11:00

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.


Date :
14 mai
Heure :
10:00 - 11:00
Catégories d’évènement:
, , ,
Voir le site évènement


Etienne Grandjean


Sciences 3- S3 351