A Probabilistic Test for A-Diagnosability of Stochastic Discrete-Event Systems With Guaranteed Error Bound

This letter investigates the failure diagnosability of stochastic discrete-event systems (DES). Specifically, the A-Diagnosability (proposed by Thorsley et al., 2005) is studied, which requires every failure to be stochastically diagnosable with arbitrary probability and within a certain delay bound. The verification of A-Diagnosability was later shown to be PSPACE-Complete, and a polynomial testing algorithm likely does not exist. This letter fills this gap by providing a new necessary and sufficient condition for checking A-Diagnosability of stochastic DES, based on which a probabilistic test is also proposed. The complexity of the proposed algorithm is polynomial in the number of system states and events, with a sacrifice that the proposed test will also incur certain test errors. Furthermore, the balance between computing complexity and probability of test error is calibratable through a hyper-parameter. Several working examples are provided to illustrate the proposed verification condition and probabilistic test.