An optimal testing technique for finite state machines

This paper presents an algorithm able to generate test sequences for real-time and embedded systems. This algorithm is divided into 3 steps. The first step is less complex than the second one which has lower complexity than the third. The first step is able to generate test sequences for some states in the system. The second step generates test sequences for some of the remaining states. The last step derives test sequences for the states which have not been covered by the two first steps. Then, we analyse a large number of experiments based on this algorithm with different automata, and we deduce that in most of the cases the first step generates test sequences for almost 85 % of all states while the second derives approximatively 10 % and finally the third one derives for 5 % of the states. That proves the efficiency of our methodology since we have no mean to prove formally these results.