On Effective Computation of Supremal Local Supports

In distributed diagnosis it may be useful to achieve local consistency among local estimates. For that purpose, the computational procedure for local consistency (CPLC) was proposed to achieve the supremal local support, which represents one type of local consistency. It has been shown that if CPLC terminates then the result is in fact the supremal local support. However, in this paper it is shown that, even if all initial estimates are regular languages, the termination of CPLC is undecidable. Moreover, these difficulties are not confined to this specific procedure: it is undecidable whether the supremal local support corresponding to an arbitrary collection of regular initial languages is componentwise empty; consequently, the supremal local support is effectively uncomputable. On the other hand, a sufficient condition is given which guarantees that CPLC terminates and that the supremal local support can be computed in time linear in the number of component diagnosers.