Chargement Évènements

« Tous les Évènements

  • Cet évènement est passé

Séminaire Algorithmique : « Random Deterministic Automata With One Added Transition », Cyril Nicaud (LIGM, Univ. Paris-Est)

22 octobre 2024 / 10:45 - 11:45

Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n to 2^n. In this talk, we investigate this classical result in a probabilistic setting where we take a random deterministic automaton with n states and add just one random transition.

This is join work with Arnaud Carayol, Philippe Duchon and Florent Koechlin.

Détails

Date :
22 octobre 2024
Heure :
10:45 - 11:45
Catégories d’évènement:
, ,
Voir le site évènement

Organisateur

Etienne Grandjean

Lieu

Sciences 3- S3 351