A polynomial algorithm for testing diagnosability of discrete-event systems (Q4540472)

An algorithm for testing the diagnosability of a system presented via a (nondeterministic) finite state automaton \(G=( X, \Sigma , \delta , x_{0})\) (\(X\) is the set of states , \(\Sigma\) is the set of event labels, \(\delta \subseteq X \times \Sigma \times X\) is the transition relation, \(x_{0}\) is the initial state) is proposed under the suppositions that the language generated by \(G\) is live, there does not exist any cycle consisting of unobservable events only, the failures are presented via the failure assignment function \(\psi : \Sigma \to \{ F \} \cup \{ \emptyset \}\) (\(F\) is a finite set of failure types) and any failure event is an unobservable one. The proposed algorithm is based on the design of a machine \(G_{0}\) being a special type of the transitive closure of \(G\), and on the analysis of cycles of the Cartesian product of \(G_{0}\) with itself (with inputs of both copies joined together). Reviewer's comments: 1. The formula in Definition 1 is incorrect, since it is of the form \((\forall\dots)\dots (\forall\dots) \Rightarrow\dots\;\). Since Definition 1 is the basic one for the reviewed paper this blunder makes it difficult to understand the problem that is solved. 2. To make the comparison of the complexity of the proposed algorithm with the results of M. Sampath (published about eight years ago), it would not be out of place to outline briefly the problem he solved and the results he obtained.