Détails sur le séminaire

salle A. Turing CE4
3 avril 2015 - 14h00
Algorithms for language equivalence of finite automata
par Damien Pous de 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 | Plan du site | Site réalisé avec SPIP 3.1.15 + AHUNTSIC [CC License]

info visites 1801337