In this paper we study the problem of predictability in partially observable discrete event systems, i.e., the question whether an observer can predict the occurrence of a fault. We extend the definition of predictability to consider the time interval where the fault will occur: the @math -predictability does not only specify that the fault will be predicted before it occurs, but also that the predictor will be able to predict that its occurrence will occur in @math to @math observations from now. We also provide a quadratic algorithm that decides predictability of the system.
Brand 'an Briones and Madalinski presented the notions of @math -predictability and @math -predictability @cite_15 . @math -predictability is similar to our definition of @math -predictability meaning that the fault is predicted at least @math observations before the fault occurs. @math -predictability is the equivalent of our property of @math -predictability, meaning that it is possible to predict the fault occurrence before it occurs but when at most @math observations are still possible before the fault (in other words, the fault prediction is not too early).
@cite_15
2329723054
A discrete event system that is predictable can anticipate faults and act accordingly. However, bare predictability (as found in the literature) has some drawbacks. One does not know exactly when a fault occurs (it could be immediately or long after it is predicted). We propose lower and upper bound refinements of predictability, called (lb; ub)-predictability. A lower bound guarantees a fault to occur after certain execution steps, whereas an upper bound guarantees a fault to occur, in the future, but before some steps. This information can be exploited by the system to adopt the best contingency plan. We formally define the notions of lb-predictability and ub-predictability, present a decision algorithm to verify it on arbitrary systems, and illustrate them with examples.