Complete open-state testing of limitedly nondeterministic systems

An approach to the problem of complete testing is proposed. Testing is interpreted as the check of an implementation’s conformance to the given requirements described by a specification. The completeness means that a test suite finds all the possible implementation errors. In practice, testing must end in a finite amount of time. In the general case, the requirements of completeness and finiteness contradict each other. However, finite complete test suites can be constructed for certain classes of implementations and specifications provided that there are specific test capabilities. Test algorithms are proposed for finite specifications and finite implementations with limited nondeterminism for the case of open-state testing. The complexity of those algorithms is estimated.