Coinduction and automata algorithms

November 20, 2017

Damien Pous (ENS Lyon)

We’ll present a simple algorithm for checking language equivalence of
non-deterministic finite automata. This algorithm can be exponentially
faster than the pre-existing ones, and it exploits a technique from
concurrency theory: `bisimulations up to congruence’. We’ll then
present recent developments on the abstract theory underlying such a
technique.