Polynomial time verification of decentralized diagnosability of discrete event systems

Failure diagnosis is an important task in large complex systems and as such this problem has received in the last years considerable attention in the literature. The first step to diagnose failure occurrences in discrete event systems is the verification of the system diagnosability. Several works in the literature have addresses this problem using either diagnosers or verifiers for the centralized and decentralized architectures. In this paper a new polynomial time algorithm to verify the decentralized diagnosability property of a discrete event system is proposed. The algorithm has lower computational complexity than other methods proposed in the literature and can also be applied to the centralized case.