ON NOISELESS DIAGNOSIS

Let F be the fault of a system which takes value in OMEGA = {f(i)}, and p(i) be the known probability of occurrence of f(i). Let T = {t(j)} be a sufficient set of tests available for diagnosing the system, and c(j) be the cost of t(j). The number of possible responses for each test in T may be different. We introduce the cost-entropy function as an information-theoretic lower bound on C(min), the expected cost of an optimal testing tree. We also obtain a universal upper bound of C(min) when {p(i)} is unknown, and a refined upper bound on C(min) when {p(i)} is known. Our results are essential for developing heuristic strategies to search for optimal and suboptimal testing trees.