[Infolix] [LABOLIX] Reminder: Comete-Parsifal Seminar Tue Jan 17, 14:30

Comete-Parsifal Seminar

Tue Jan 17, 14:30
LIX, Ecole Polytechnique, Aile 0
Salle de Reunion, LIX
http://www.lix.polytechnique.fr/comete/seminar/

Lien pour accéder au campus :
http://www.polytechnique.edu/accueil/vie-sur-le-campus/acceder-au-campus/
Link to reach the campus:
http://www.polytechnique.edu/home/life-on-campus/arriving-on-campus/

Title: Checking NFA equivalence with bisimulations up to congruence.
Speaker: Filippo Bonchi.
Abstract:
We introduce bisimulation up to congruence as a technique for proving
language equivalence of non-deterministic finite automata. Exploiting this
technique we devise an optimization of the classical algorithm by Hopcroft
and Karp that, instead of computing the whole determinized automata,
explores only a small portion of it. Although the optimized algorithm
remains exponential in worst case (the problem is PSPACE-complete),
experimental results show improvements of several orders of magnitude over
the standard algorithm.
Joint work with Damien Pous.

©Copyright LIX 2013
Powered by Pyramid
Layout based on Yaml