Failure prognosability of stochastic discrete event systems

We study the prognosis of fault, i.e., its prediction prior to its occurrence, in stochastic discrete event systems. We introduce the notion of m-steps Stochastic-Prognosability, called S_m-Prognosability, which allows the prediction of a fault at least m-steps in advance. We formalize the notion of a prognoser and also show that S_m-Prognosability is necessary and sufficient for the existence of a prognoser that can predict a fault at least m-steps prior to occurrence, while achieving any arbitrary false alarm and missed detection rates. We also provide a polynomial algorithm for the verification of S_m-Prognosability.