IEEE Transactions on Automatic Control, Vol.61, No.1, 178-181, 2016
"Polynomial time verification of decentralized diagnosability of discrete event systems" vs. "Decentralized failure diagnosis of discrete event systems": A critical appraisal
In [1] the authors claim that there is an oversight in [2], in the sense that the proposed verifier is, in general, nondeterministic and the computational complexity analysis is incorrect. The authors in [1] also claim that the complexity of the verification algorithm presented in [3] is reduced when considering the more restrictive setting of projection masks, in contrast to the more general non-projection masks case, and equals the complexity of the verification algorithm presented in [2]. In this note, we show that the computational complexity analysis of [2] is actually correct and that the complexity of the verification algorithm presented in [3] is not reduced without additional modification of the algorithm (not yet proposed in the literature) if projection masks are used, and, therefore, is not equal to the complexity of the algorithm presented in [2].