Predictability of event occurrences in partially-observed discrete-event systems

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.