Optimal transfer trees and distinguishing trees for testing observable nondeterministic finite-state machines

The fault-state detection approach for blackbox testing consists of two phases. The first is to bring the system under test (SUT) from its initial state to a targeted state t and the second is to check various specified properties of the SUT at t. This paper investigates the first phase for testing systems specified as observable nondeterministic finite-state machines with probabilistic and weighted transitions. This phase involves two steps. The first step transfers the SUT to some state t' and the second step identifies whether t' is indeed the targeted state t or not. State transfer is achieved by moving the SUT along one of the paths of a transfer tree (TT) and state identification is realized by using diagnosis trees (DT). A theoretical foundation for the existence and characterization of TT and DT with minimum weighted height or minimum average weight is presented. Algorithms for their computation are proposed.