Inference-diagnosability: Nonconvergence and other complexity results

A framework for the inference-based decentralized diagnosis of discrete event systems was reported in our prior work. The notion of N-inference F-diagnosability was formulated to characterize the class of diagnosable systems in this framework. This property ensures that the ambiguity levels of diagnosis decisions are at most N. A system is said to be inference F-diagnosable if it is N-inference F-diagnosable for some N, i.e., if the number of levels of inferencing required is bounded. In this paper we answer an open question that even in the setting of finite-state plant and specification models, the number of levels of inferencing required is in general unbounded. The following additional results are obtained. We show that the class of N-inference F-diagnosable systems increases strictly monotonically as the parameter N is increased. We also show that the inference F-diagnosability is strictly stronger than the decentralized-diagnosability.