A linear algorithm for testing equivalence of finite automata
An algorithm is given for determining if two finite automata with start states are equivalent. The asymptotic running time of the algorithm is bounded by a constant times the product of the number of states of the larger automation with the size of the input alphabet. (Author).
What people are saying - Write a review
We haven't found any reviews in the usual places.
ALGORITHM FOR TESTING algorithm is bounded algorithm is given algorithm starts assume asymptotic running AUTOMATA J. E. Hopcroft California Berkeley Clearly connecting sequence constant Cornell University Ithaca equivalence of finite equivalence relation equivalent to M2 Execute the instruction final and nonfinal find instruction FINITE AUTOMATA J. E. given for determining hence Hopcroft Cornell University Induction hypothesis input alphabet input symbols integer J. E. Hopcroft Cornell kth execution larger automaton Lemma LINEAR ALGORITHM linear list merging list contains list merging algorithm lists are merged Naval Research Notation number of pairs Office of Naval pairs popped place the pair prior Proof pushdown store q are joined qQ and pQ R. M. Karp University remains to show right invariant sequence of merge set containing set named single automaton single set Step TESTING EQUIVALENCE testing the equivalence Theorem timet Unclassified University of California York R. M. Karp