TESTING FINITE-STATE MACHINES - FAULT-DETECTION

We present simple randomized algorithms for the fault detection proble m: Given a specification in the form of a deterministic finite state m achine A and an implementation machine B, determine whether B is equal to A. If A has n states and p inputs, then in randomized polynomial t ime we can construct with high probability a checking sequence of leng th O(pn(4) log n), i.e., a sequence that detects all faulty machines w ith at most n states. Better bounds can be obtained in certain cases. The techniques generalize to partially specified finite state machines . (C) 1995 Academic Press. Inc.