Jeudi 8/11 à 11h en salle 1D06, séance séminaire PPS avec Damien Pous

Bonjour,

Comme annoncé lors de la dernière séance du séminaire, nous accueillerons Damien Pous ce jeudi 8 novembre qui viendra nous présenter un article accepté à POPL'13 intitulé Checking NFA equivalence with bisimulations up to congruence (co-écrit avec Filippo Bonchi).

Le séminaire intéressera aussi bien les membres de PPS que ceux du LIAFA.

La séance aura lieu Jeudi 8/11 à 11h en salle 1D06 et nous vous rappelons que café et thé seront servis dès 10h45 dans la salle du séminaire où nous espérons vous voir nombreux.

Checking NFA equivalence with bisimulations up to congruence
Damien Pous (CNRS & ENS-Lyon)
Jeudi 8/11 à 11h en salle 1D06
http://www.pps.univ-paris-diderot.fr/seminaire/sem2012/abstracts/Pous

Résumé: 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".


Cordialement,
L'équipe du Séminaire