[Infolix] [LABOLIX] Reminder: Comete-Parsifal Seminar Tue Jan 17, 14:30
Tue Jan 17, 14:30
LIX, Ecole Polytechnique, Aile 0
Salle de Reunion, LIX
Lien pour accéder au campus :
Link to reach the campus:
Title: Checking NFA equivalence with bisimulations up to congruence.
Speaker: Filippo Bonchi.
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.