Uncomputability of Supremal Local Supports in Distributed Diagnosis
J.G. Thistle, Rong Su · 2006
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.