A New Perspective on Conformance Testing Based on Apartness

We revisit the classic problem of black box conformance testing and present a generalization of the k-completeness result of Vasilevskii and Chow, phrased entirely in terms of properties of the observation/prefix tree induced by a test suite, in particular in terms of apartness relations between states. The original result of Vasilevskii and Chow is then a corollary of our result. Also k-completeness results for other test methods that have been proposed in the literature, such as the Wp-method and the HSI-method, follow from our characterization. Based on the apartness relations in the observation tree, we may determine whether some test is redundant or can be shortened.