On the global optimization of checking sequences for finite state machine implementations

A checking sequence for a given domain of deterministic finite state machine implementations is an input sequence for which exactly the non-faulty members of the domain produce a non-faulty response. In the paper, we reconsider a popular family of methods which construct a checking sequence by performing its digraph-based global optimization. Recently, it was demonstrated that many of the methods are unsafe. As a remedy, a simple, but sufficient set of additional constraints on the structure of the employed digraph was introduced. In this paper, we show that the constraints sometimes ban also some of those originally considered checking sequence candidates which are sound. To safely restore the original power of the checking sequence construction approach, we perform its thorough re-engineering. This results in a very transparent and flexible generic method from which various methods of practical interest, both new ones and analogues of the traditional ones, can be derived simply by specialization.