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
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.