An Improved Bound for Checking Experiments that Use Simple Input-Output and Characterizing Sequences

The least upper bound of n(n−1)/2 input symbols is derived for the total length of characterizing sequences for a reduced n-state machine. When a machine can be characterized by a set of r characterizing sequences, a reduced upper bound on their total length will be r(2n−r−1)/2 input symbols. To shorten transfer sequences, better use is made of the strong-connectedness assumptions of the machines to be tested. The reduced bounds on characterizing and transfer sequences are utilized to improve the upper bounds on checking experiments employing simple input/output (I/O) sequences.