Observation-Subsumption Checking in Similarity-Based Diagnosis of Discrete-Event Systems

In similarity-based diagnosis of discrete-event systems the knowledge generated for solving a previous diagnostic problem can be reused to solve a new one, provided the two problems are similar. Problem-similarity requires that the temporal observation relevant to the new problem be subsumed by the temporal observation relevant to the old one. A temporal observation encompasses the (uncertain) events observed over a time interval and their (uncertain) reciprocal temporal order. Such an observation has been produced by one out of several distinct certain sequences of observable events, with each of such sequences being a sentence of the regular language of the observation. An observation subsumes another if its regular language contains the regular language of the other. However, checking observation-subsumption by following its formal definition is time consuming. In order to speed up the process, an alternative technique is proposed, which is based on the notion of coverage and exploits a number of necessary conditions, as well as a sufficient condition, for subsumption to hold. Such conditions can be directly checked on the properties of the given observations, without any need to appeal to the language theory. Experimental evidence confirms the efficiency of subsumption-checking via coverage.