Algebraic approaches for fault identification in discrete-event systems

In this note, we develop algebraic approaches for fault identification in discrete-event systems that are described by Petri nets. We consider faults in both Petri net transitions and places, and assume that system events are not directly observable but that the system state is periodically observable. The particular methodology we explore incorporates redundancy into a given Petri net in a way that enables fault detection and identification to be performed efficiently using algebraic decoding techniques. The guiding principle in adding redundancy is to keep the number of additional Petri net places small while retaining enough information to be able to systematically detect and identify faults when the system state becomes available. The end result is a redundant Petri net embedding that uses 2k additional places and enables the simultaneous identification of 2k - 1 transition faults and k place faults (that may occur at various instants during the operation of the Petri net). The proposed identification scheme has worst-case complexity of O(k(m + n)) operations where m and n are respectively the number of transitions and places in the given Petri net.