Codiagnosability of discrete event systems revisited: A new necessary and sufficient condition and its applications. (March 2019) - Viana, Gustavo S.; Basilio, João C.
Abstract: It has been argued for some time now, based on classroom, textbook and practical examples that the size of verifiers and diagnosers is comparable. This belief has been corroborated by a recent paper, where it is conjectured, based on a rigorous statistical analysis, that the size of the states of diagnosers is Θ ( n 0 . 77 log k + 0 . 63 ), on the average, where k (resp. n ) is the number of events (resp. states) of the plant automaton. However, there is another difficulty that hampers the use of diagnosers in diagnosability verification: the search for cycle, which has been proved to be factorial. We present, in this paper, a necessary and sufficient condition for a language codiagnosability of DES and, based on this condition, we propose a new test for its verification that is based on a diagnoser-like automaton that has following advantages: (i) the diagnosability verification test is based on the search for strongly connected components, which is linear in the state size; (ii) it has both observable and unobservable events of the plant in its event set, and so the usual assumptions on language liveness and nonexistence of unobservable cycles of states connected with unobservable events only are no longer required, and; (iii) T-codiagnosability can be computed by adding weights associated with transitions of the plant automaton, and, as a consequence K-codiagnosability, since it is a particular case of T-codiagnosability when all weights are set equal to 1.