Checking Sequence Generation Using State Distinguishing Subsequences

A checking sequence generated from a finite state machine (FSM) is used in testing to demonstrate correctness of an implementation under test. It can be obtained by concatenating inputs triggering state transitions followed by final state verification sequences. Usually, the latter are derived from a distinguishing set or sequence, assuming that a given FSM possesses it. It has been suggested that, under certain conditions, unique input/output (UIO) sequences can also be used. In this paper, we propose using sequences with less state distinguishability power than distinguishing and UIO sequences. Such sequences are shorter and thus can reduce the length of checking sequences. We formulate conditions under which such sequences can replace distinguishing and UIO sequences and elaborate a checking sequence generation method based on these conditions. An example is provided to demonstrate that the proposed method yields a checking sequence shorter than existing methods.