Florentin IPATE, Marian GHEORGHE, Mike HOLCOMBE, Tudor BĂLĂNESCU

A Theory of Testing for Non-Deterministic X-Machines

Abstract.

Introduced by Eilenberg, X-machines  (Eilenberg machines) were proposed by Holcombe in 1988 as a basis for a possible specification language and since then a number of further investigations have demonstrated the value of this idea. A number of classes of X-machines have been identified and studied, most importantly the class of stream X-machines.  A theory of testing based on stream X-machines has also been developed. This allows the generation of test sets that are proved to guarantee the correctness of implementation against the specification under certain circumstances. A recent paper generalises this theory to the general X-machine model and, furthermore, the results proven can form the basis of two distinct testing strategies. This paper generalises these recent results to the non-deterministic case. The generalisation is non-trivial and it can cope with all types of non-determinism that can be found in an X-machine model.