Sign In

Communications of the ACM

Research Archive


Archives

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

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…