On the complexity of single fault set diagnosability and diagnosis problems

DOI10.1109/12.16496MaRDI QIDQ3817610zbMATH OpenOpenAlexFDO

Authors Arun K. Somani, V. K. Agarwal, David Avis

Publication date 1989

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/12.16496

zbMATH Keywords

diagnosabilityfault diagnosispolynomial time complexityco-NP-completeinvalidation models

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of software (68N99)

Recommendations

• Complexity of the diagnosability problem for a general model of diagnosable systems
• Complexity and compilability of diagnosis and recovery of graph-based systems
• scientific article; zbMATH DE number 4211973
• An analysis of self-diagnosis model by conditional fault set
• scientific article; zbMATH DE number 3910312

Cited in

(6)

• Weighted diagnosis with asymmetric invalidation
• Fault identification in system-level diagnosis: A logic-based framework and an \(O(n^2\sqrt\tau / \sqrt{\log n)}\) algorithm
• Complexity and compilability of diagnosis and recovery of graph-based systems
• Symmetric PMC model of diagnosis, \(b\)-matchings in graphs and fault identification in \(t\)-diagnosable systems
• Complexity of the diagnosability problem for a general model of diagnosable systems
• An 0(n^2.5) Fault Identification Algorithm for Diagnosable Systems

This page was built for publication: On the complexity of single fault set diagnosability and diagnosis problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3817610)