Generating Candidates When Testing a Deterministic Implementation against a Non-deterministic Finite-state Machine

This paper considers the problem of testing a deterministic system against a non-deterministic finite-state machine. An adaptive test process, with two phases, is proposed. The paper focuses on the first stage which involves testing to generate a candidate deterministic finite-state machine. This candidate has the property that, under the test hypotheses used, the implementation is correct if and only if it is equivalent to the candidate. A test may then be derived from the candidate.