Polynomial Test for Stochastic Diagnosability of Discrete-Event Systems

Two types of diagnosability of stochastic discrete-event systems (DESs) were introduced by Thorsley et al. in 2005, where a necessary and sufficient condition for Strong Stochastic (SS)-Diagnosability (referred as A-diagnosability by Thorsley and Teneketzis, 2005), and a sufficient condition for Stochastic (S)-Diagnosability (referred as AA-diagnosability by Thorsley and Teneketzis, 2005), both with exponential complexity, were reported. In this paper, we present polynomial complexity tests for checking: (i) necessity and sufficiency of SS-Diagnosability; (ii) sufficiency of S-Diagnosability; and (iii) sufficiency as well as necessity of S-Diagnosability; the latter requires an additional notion of probabilistic equivalence. Thus, the work presented improves the accuracy as well as the complexity of verifying stochastic diagnosability.