Computation of synchronous diagnosis bases of discrete-event

Several works have been proposed to address fault diagnosis of Discrete-Event Systems (DES) considering different approaches and architectures. In the vast majority, the fault diagnoser is constructed based on the complete system model, which may have a huge number of states, due to the parallel composition of several modules. The implementation of diagnosers with a large number of states consumes a large amount of computer memory, and may become, in some cases, unfeasible. Recently, synchronous diagnosis of DES has been proposed, where state observers of fault-free models of system modules are used for fault diagnosis. The method provides a diagnoser that is not based on the composed plant model, which leads to a diagnoser with fewer states and transitions than the classical diagnoser. In the synchronous diagnosis approach, all the subsystem models are assumed to contribute to fault detection. However, in practice, certain subsystems may not provide useful information on fault occurrences, or redundant information may be available from other modules. Consequently, these redundant modules are not necessary in the synchronous diagnosis scheme and can be discarded, leading to reduced diagnosers. In this paper, we present a method for computing a synchronous diagnoser that uses only part of the subsystem models. It is also shown that the fault can be diagnosed using modules where the fault event is not even modeled. To do so, we present an algorithm for computing all the sets of modules that ensure the synchronous diagnosability of a DES. These sets are called synchronous diagnosis bases (SDB). We prove that the complexity of the problem of finding an SDB with cardinality less than or equal to a given natural number is NP-complete. Thus, the algorithm proposed in this work has the objective of mitigating the computational efforts to find all the SDB of a DES. Two examples are used to illustrate the efficiency of the proposed method.