Diagnosis of repeated failures in discrete event systems

We introduce the notion of repeated failure diagnosability for diagnosing the occurrence of a repeated number of failures in discrete event systems. This generalizes the earlier notion of diagnosability that was used to diagnose the occurrence of a failure, but from which the information regarding the multiplicity of the occurrence of the failure could not be obtained. It is possible that in some systems the same type of failure repeats a multiple number of times. It is desirable to have a diagnoser which not only diagnoses that such a failure has occurred but also determines the number of times the failure has occurred. To aide such analysis we introduce the notions of K-diagnosability (K failures diagnosability), [1,K]-diagnosability (1 through K failures diagnosability), and [1, ∞]-diagnosability (1 through ∞ failures diagnosability). Here the first (resp., last) notion is the weakest (resp., strongest) of all three, and the earlier notion of diagnosability is the same as that of K-diagnosability or that of [1,K]-diagnosability with K = 1. We give polynomial algorithms for checking these various notions of repeated failure diagnosability, and also present a procedure of polynomial complexity for the on-line diagnosis of repeated failures.