Maestrini P. Complexity aspects of system diagnosis. Internal note IEI-B79-22, 1979. |

Abstract (English) |
Two relevant problems in the diagnostic model af Preparata. Metze and Chien consist in identifying classes of optimal sequentially diagnosable systems and in evaluating the complexity of syndrome decoding for sequential diagnosis. The problem of determining optimal sequentially diagnosable systems is still unsolved except for the cases when the diagnosability equals the smallest or the largest permissible value; and the known bounds to the complexity of optimal systems are supposed to be quite weak. Further, the problem of syndrome decoding is known to be NP-complete in the general case. A class of diagnostic systems is introduced, whose members attain all permissible values of sequential diagnosability. It is shown that the upper bound to complexity of optimal system established by such class is tighter than those previously known, and complexity of syndrome decoding is O(/V/), where /V/ is the number af units. | |

Subject |

1) Download Document PDF |

Open access Restricted Private