Optimal and Near-Optimal Checking Experiments for Output Faults in Sequential Machines

Abstract

An algorithmic procedure for designing optimal and near-optimal checking sequences for output faults is presented. For the specific cases where minimum length cannot be guaranteed, the algorithm also determines an upper bound on the excess length of the resulting sequence. Several extensions of the method are discussed, such as the application of output checking sequences for diagnosing purposes. The possibilities of this approach in the search for algorithms that yield optimal checking sequences for more general classes of faults are illustrated by applying the method in an ad hoc fashion and obtaining a complete checldng experiment.