A polynomial algorithm for testing diagnosability of stochastic discrete event systems

Failure diagnosis in large and complex systems is a crucial task. In this paper, we propose a polynomial algorithm for testing A-diagnosability (the idea is that a failure can be diagnosed after a finite delay was not “all-or-nothing” propositions, but had a certain probability) of stochastic discrete event systems. We construct a stochastic diagnoser by appending to each transition a vector that can be used to update the probability of the event occurring. A necessary and sufficient condition for A-diagnosability is obtained by properties of the stochastic diagnoser which is not a stochastic automaton, but possesses a structure superficially similar to one. Moreover, some examples are given to illustrate the results.