Improved heuristics for W-set and K-tree generation on finite state machines

Finite State Machine (FSM) based testing methods utilize State Identification Sequences which are used to identify the states of a black box implementation as corresponding to the states of an FSM given as the specification. There are different types of state identification sequences. Some of these state identification sequences are not guaranteed to exist for all specifications. There is one particular type of state identification sequences, W-set based state identification sequences, which are known to exist for any minimal, deterministic, completely specified FSM. Although W-set based state identification sequences are known for a very long time, most of the works in FSM based testing literature do not prefer to use them when testing for an implementation without a reliable reset feature, since the length of W-set based state identifications sequences in this case are exponential in the cardinality of the W-sets. There are some recent works that suggest reducing the length of the W-set based state identification sequences. In fact, instead of W-sets, which are sets of preset experiments, these new methods can make use of so-called K-sets, which are set of adaptive experiments that again always exist. Furthermore, these new methods suggest applying not all elements of W–sets/K-sets, but instead an adaptive structure, called a K-tree is used to orchestrate the application of the elements of the K-set. However, there are no extensive experimental studies for these new methods. In addition, no algorithms are given for the construction of K-trees. In this work, we first present some W-set construction algorithms to construct better W-sets, in terms of both the cardinality and the total length of the sequences. We compare our W-set algorithms experimentally to the algorithms that exist in the literature. We also present algorithms to constructs K-sets and K-trees. Finally, we present an extensive experimental study for state identification sequences. The results show that, although W-set based state identification sequences have been considered practically infeasible due to the exponentially long sequences, the usage of K-trees make state identification sequences very short and practically usable. Utilizing K–sets in the generation of K–trees also yields better results than utilizing W–sets