Random Deterministic Automata With One Added Transition

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.