salle A. Turing CE4
3 April 2015 - 14h00
Algorithms for language equivalence of finite automata
by Damien Pous from ENS de Lyon
Abstract: Finite automata are used in a wide range of verification problems.
We introduce "bisimulation up to congruence" as a technique for
proving language equivalence of non-deterministic finite automata.
Exploiting this technique, we devise an optimisation of the classical
algorithm by Hopcroft and Karp which, as we show, is exploiting a
weaker "bisimulation up to equivalence" technique. The resulting
algorithm can be exponentially faster than the recently introduced
"antichain algorithms".
