Predictability of Failure Event Occurrences in Decentralized Discrete-Event Systems and Polynomial-Time Verification

Due to the practical and theoretical importance, failure prediction of discrete-event systems (DESs) has received increasing attention recently. In this paper, the predictability of failure events in decentralized DESs is investigated. The main contributions are as follows. First, the notion of copredictability of DESs is formalized under the decentralized framework to capture the feature that the occurrences of failure events can be predicted based on at least one local observation. It is deducted that the copredictability is weaker than the predictability but stronger than the codiagnosability. Second, in order to achieve the performance of prediction, a nondeterministic automaton called coverifier is constructed from the given system. Third, the necessary and sufficient condition for verifying the copredictability of DESs based on the coverifier is presented, which generalizes the main results by Genc and Lafortune from the centralized systems to the decentralized setting. It is worth noting that both constructing the coverifier and verifying the copredictability can be realized with polynomial complexity in the number of states and events of the system.