New state-recognition patterns for conformance testing of finite state machine implementations

In black-box conformance testing of reactive systems, the system is often assumed to be an implementation of a given finite state machine and to possess no more states than the machine. The key activity in the interpretation of an input/output sequence observed on the system is then to recognize the visited states as states of the specification machine. In the paper, three traditional state-recognition patterns (SRPs) are generalized to two much stronger, but still relatively easy to apply SRPs, and further to an extremely strong and general SRP from which further practically interesting SRPs can be developed simply by specialization.

► The concept of distinguishers is introduced.
► Traditional state recognition exploits only singleton distinguishers.
► It is helpful to exploit also non-singleton distinguishers.
► It is helpful to exploit also collections of distinguishers.
► It is helpful to simultaneously exploit distinguishers and system determinism.