Improved Diagnosability Algorithms

We present improved one-step diagnosability algorithms for both the BGM and PMC models. Using the letters n, m, and r to denote the number of units, the number of tests, and the diagnosability number, respectively, the results of the paper can be summarized as follows: in the BGM model, our algorithm has a complexity of [formula Omitted] improving on Narasimhan and Nakajima’s O (nr³⁾algorithm; in the PMC model, our algorithm has a complexity of O(nr^2.5) improving on Sullivan’s O(mn^1.5) algorithm. Further, the ideas used in our algorithm for the PMC model can be easily extended to improve Sullivan’s algorithms for determining the t/t + k diagnosability numbers.