Seminar details


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.




Contact | Site Map | Site powered by SPIP 4.2.8 + AHUNTSIC [CC License]

info visites 3902204