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_13: Abstract: This paper studies the problem of predicting occurrences of a significant event in a discrete-event system. The predictability of occurrences of an event in a system is defined in the context of formal languages. The predictability of a language is a stronger condition than the diagnosability of the language. An implementable necessary and sufficient condition for predictability of occurrences of an event in systems modeled by regular languages is presented.
  @cite_3: This paper studies the problem of predicting occurrences of a significant event in a partially-observed discrete-event system. The predictability of occurrences of an event in a system is defined in the context of formal languages. The predictability of a language is a stronger condition than the diagnosability of the language. Two necessary and sufficient conditions for predictability of occurrences of an event in systems modeled by regular languages are presented. Both conditions can be algorithmically tested. The first condition employs diagnosers. The second condition employs verifiers and results in a polynomial-time (in the number of states) complexity test for verification of predictability. When predictability holds, diagnosers can be used online to predict the significant event.
summary: Predictability as presented in this paper was introduced by Genc and Lafortune @cite_13 . Their approach was however only Boolean: they addressed the question can the fault be predicted before it occurs?'' They presented an exponential space algorithm using a structure similar to our optimal predictor. They also announced the existence of a polytime algorithm, similar to the twin plant used for diagnosability and formally presented in an extension of their work @cite_3 .