2013 · 150 citations · 19 references
ComputingComputer ScienceAlgorithmsFormal MethodsTheory Of ComputationAutomata TheoryEquivalence CheckingFinite AutomataFinite-state MachinesModel CheckingVerificationAutomata In Formal VerificationAutomata-based Equivalence CheckingBisimulation AnalysisCongruence ProofsFinite Automata TheoryFinite State Machine VerificationLanguage EquivalenceNondeterministic Finite Automata
We introduce bisimulation up to congruence as a technique for proving language equivalence of non-deterministic finite automata. Exploiting this technique, we devise an optimisation of the classical algorithm by Hopcroft and Karp. We compare our approach to the recently introduced antichain algorithms, by analysing and relating the two underlying coinductive proof methods. We give concrete examples where we exponentially improve over antichains; experimental results moreover show non negligible improvements.
19
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
Word problems requiring exponential time(Preliminary Report)
Larry J. Stockmeyer, Albert R. Meyer · 1973 · 874 citations
Computing simulations on finite and infinite graphs
Monika Henzinger, Thomas A. Henzinger, Peter W. Kopke · 2002 · 479 citations
Towards a mathematical operational semantics
Daniele Turi, Gordon Plotkin · 2002 · 369 citations · Full text