On the complexity of single fault set diagnosability and diagnosis problems

DOI10.1109/12.16496zbMATH Open0666.68044OpenAlexW2117911965MaRDI QIDQ3817610FDOQ3817610

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

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

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
• An analysis of self-diagnosis model by conditional fault set
• scientific article; zbMATH DE number 3910312

zbMATH Keywords

diagnosabilityfault diagnosispolynomial time complexityco-NP-completeinvalidation models

Mathematics Subject Classification ID

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

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)