Comments on “Polynomial Time Verification of Decentralized Diagnosability of Discrete Event Systems” versus “Decentralized Failure Diagnosis of Discrete Event Systems”: Complexity Clarification

An article on codiagnosability verification of discrete event systems was reported by Moreira et al, claiming an improvement in complexity over a paper by Qiu and Kumar. This note clarifies an oversight in the complexity analysis of Moreira et al´s paper. Further the results of Moreira et al´s paper were obtained in a more restricted setting of “projection masks”, in contrast to the more general “non-projection masks” allowed in Qiu and Kumar´s paper, which was overlooked. Finally in the special case when the projection masks are used, the complexity of Qiu and Kumar´s paper is lower compared to the non-projection masks case, and equals the corrected complexity of Moreira et al´s paper.