ACombining centralised and distributed testing

Many systems interact with their environment at distributed interfaces (ports) and sometimes it is not pos-sible to place synchronised local testers at the ports of the system under test (SUT). There are then two main approaches to testing: having independent local testers or a single centralised tester that interacts asynchronously with the SUT. The power of using independent testers has been captured using implemen-tation relation dioco. In this paper we define implementation relation diococ for the centralised approach and prove that dioco and diococ are incomparable. This shows that the frameworks detect different types of faults and so we devise a hybrid framework and define an implementation relation diocos for this. We prove that the hybrid framework is more powerful than the distributed and centralised approaches. We then prove that the Oracle problem is NP-complete for diococ and diocos but can be solved in polynomial time if we place an upper bound on the number of ports. Finally, we consider the problem of deciding whether there is a test case that is guaranteed to force a finite state model into a particular state or to distinguish two states, proving that both problems are undecidable for the centralised and hybrid frameworks