?
Deriving Adaptive Homing Sequences for Weakly Initialized Nondeterministic FSMs
Abstract——State identification sequences, such as homing
and distinguishing sequences (HS and DS), are widely used in FSM
(Finite State Machine) based testing in order to reduce the size of
a returned complete test suite as well as minimize checking efforts
in passive testing. Preset HS are known to always exist for
deterministic complete reduced FSMs but it is not the case for
nondeterministic FSMs. It is also known that in this case, adaptive
HS exist more often and usually are shorter than the preset.
Nowadays, a number of specifications are represented by
nondeterministic FSMs and thus, a deeper study of such sequences
is required. There exist sufficient and necessary conditions for the
existence of an adaptive HS for complete nondeterministic FSMs
when each state can be an initial state but those conditions become
only sufficient for weakly initialized FSMs where only some states
are initial. In this paper, we propose sufficient and necessary
conditions for a weakly initialized FSM to have an adaptive
homing sequence, possibly up to given length, which are based on
deriving an appropriate so-called homing FSM. The experimental
evaluation of the existence of adaptive and preset HS is performed
for randomly generated FSMs.