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.

Complexity aspects of system diagnosis

1979

Abstract

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.
1979
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - ISTI
system diagnosis
File in questo prodotto:
File Dimensione Formato  
prod_421899-doc_149903.pdf

accesso aperto

Descrizione: Complexity aspects of system diagnosis
Dimensione 1.26 MB
Formato Adobe PDF
1.26 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/411005
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact