Cover Image
QR Code

Hacking Nondeterminism with Induction and Coinduction.

We introduce bisimulation up to congruence as a technique for proving language equivalence of nondeterministic finite automata. Exploiting this technique, we devise an optimization of the classic algorithm by Hopcroft and Karp. We compare our approach to the recently introduced antichain algorithms...

Full description

Published in:Communications of the ACM Vol. 58; no. 2; pp. 87 - 96
Main Authors: Bonchi, Filippo, Pous, Damien
Format: Article
Published: Association for Computing Machinery Feb2015
Subjects:
Machine theory
Algorithms
Bisimulation
Coinduction (Mathematics)
Programming languages
Program transformation
Online Access:View this record in EBSCOhost

Internet

View this record in EBSCOhost