
- 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.