text: 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.
  @cite_8: Abstract The problem of predicting the occurrences of a pattern in a partially-observed discrete-event system is studied. The system is modeled by a labeled transition system. The pattern is a set of event sequences modeled by a finite-state automaton. The occurrences of the pattern are predictable if it is possible to infer about any occurrence of the pattern before the pattern is completely executed by the system. A novel off-line algorithm to verify the property of predictability is presented. The verification is polynomial in the number of states of the system. An on-line algorithm to track the execution of the pattern during the operation of the system is also presented. This algorithm is based on the use of a diagnoser automaton.
summary: Together with J 'eron and Marchand, they proposed an additional improvement to lower the complexity down to quadratic @cite_8 . We claim here that their algorithm is not quite quadratic (we discuss this question at the end of this section). Their approach is very similar to the approach presented in the previous section: They construct a twin plant and verify predictability by checking whether there exists a pair @math such that @math and @math .