Verification of Pattern-Pattern Diagnosability in Partially Observed Discrete Event Systems

This work studies a new notion of diagnosability called the pattern-pattern diagnosability in discrete event systems modeled by partially observable finite state automata. Suppose that in the system there are some sequences of events that are undesirable to happen, which we call the fault pattern. We want to determine whether the occurrence of the fault pattern can be determined before some sequences - -which we call the critical pattern and may cause fatal consequences after the fault pattern - are completed. Both fault and critical patterns are assumed to be regular and, hence, are described by the languages accepted by finite automata. We propose a novel notion of pattern-pattern diagnosability (PP-diagnosability), which requires that the occurrence of a fault pattern can always be detected before the completion of a critical pattern thereafter. The properties of PP-diagnosability, and the relations between PP-diagnosability and conventional diagnosability are studied. Then, we propose a method to verify PP-diagnosability using a structure called the pattern-pattern verifier. The complexity of the proposed method is polynomial in the number of states of the plant and the two pattern automata.