Fault Identification in System‐Level Diagnosis: a Logic‐Based Framework and an O(n2\sqrt{t}/{\log n}) Algorithm

Much research has been devoted to system‐level diagnosis–SLD. Two issues have been addressed. The first of these is diagnosability, i.e., provide necessary and sufficient conditions for a system of n units to be diagnosable provided that the number of faulty units does not exceed τ . The second is the design of fault identification algorithms, assuming that the system being considered is diagnosable. This paper focuses on the second of these concerns, discussing several algorithms of which the most efficient runs in O(n ^2.5 ) . By considering a logical framework, this paper investigates the process of fault identification and proposes a fault identification algorithm which runs in O( n ² \sqrt τ / \sqrt log n ) , τ < n/2 .