Verimag

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.0.26 + AHUNTSIC [CC License]

info visites 873069