TESTING FINITE-STATE MACHINES - STATE IDENTIFICATION AND VERIFICATION

We study the complexity of two fundamental problems in the testing of finite-state machines. 1) Distinguishing sequences (State Identificati on). We show that it is PSPACE-complete to determine whether a finite- state machine has a preset distinguishing sequence. There are machines that have distinguishing sequences, but only of exponential length. W e give a polynomial time algorithm that determines whether a finite-st ate machine has an adaptive distinguishing sequence. (The previous cla ssical algorithms take exponential time.) Furthermore, if there is an adaptive distinguishing sequence, then we give an efficient algorithm that constructs such a sequence of length at most n(n-1)/2 (which is t he best possible), where n is the number of states. 2) Unique Input Ou tput sequences (State Verification). It is PSPACE-complete to determin e whether a state of a machine has a unique input output sequence. The re are machines whose states have unique output sequences but only of exponential length.