Communications of the ACM
Research Archive
The Research archive provides access to all Research articles published in past issues of Communications of the ACM.
February 2015
From Communications of the ACM
Hacking Nondeterminism with Induction and Coinduction
We introduce bisimulation up to congruence as a technique for proving language equivalence of nondeterministic finite automata.
From Communications of the ACM
Technical Perspective: The Equivalence Problem For Finite Automata
As the equivalence problem is essential in many applications, we need algorithms that avoid the worst-case complexity as often as possible. In "Hacking Nondeterminism with Induction and Coinduction," Filippo Bonchi and Damien…