Report Number: CSL-TR-72-30
Institution: Stanford University, Computer Systems Laboratory
Title: Adaptive design methods for checking sequences
Author: Boute, Raymond T.
Date: July 1972
Abstract: The length of checking sequences for sequential machines can be considerably reduced if, instead of preset distinguishing sequences, one uses so-called distinguishing sets of sequences, which serve the same purpose, but are generally shorter. The design of such a set turns out to be equivalent to the design of an adaptive distinguishing experiment,* though a checking sequence, using a distinguishing set, remains essentially preset. This property also explains the title. All machines having preset distinguishing sequences also have distinguishing sets. In case no preset distinguishing sequences exist, most of the earlier methods call for the use of locating sequences, which result in long checking experiments. However, in many of these cases, a distinguishing set can be found, thus resulting in even more savings in length. Finally, the characterizing sequences used in locating sequences can also be adaptively designed, and thus the basic idea presented below is advantageous even when no distinguishing sets exist. By "experiment" we mean the application of sequence(s) to the machine while observing the output. In some instances, the words "experiment" and "sequence" can be used interchangeably.
http://i.stanford.edu/pub/cstr/reports/csl/tr/72/30/CSL-TR-72-30.pdf