On the Computational Complexity of System Diagnosis
- 1 October 1978
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-27 (10) , 881-885
- https://doi.org/10.1109/tc.1978.1674966
Abstract
In this paper we analyze the computational complexity of system diagnosis. We show that several problems for instantaneous and sequential fault diagnosis of systems are polynomially complete and that for single-loop systems these problems are solvable in polynomial time.Keywords
This publication has 11 references indexed in Scilit:
- System Diagnosis and Redundant TestsIEEE Transactions on Computers, 1976
- A Theory of Diagnosability of Digital SystemsIEEE Transactions on Computers, 1976
- On Models for Diagnosable Systems and Probabilistic Fault DiagnosisIEEE Transactions on Computers, 1976
- A diagnosing algorithm for networksInformation and Control, 1975
- An Approach to the Diagnosability Analysis of a SystemIEEE Transactions on Computers, 1975
- Polynomially Complete Fault Detection ProblemsIEEE Transactions on Computers, 1975
- Computationally Related ProblemsSIAM Journal on Computing, 1974
- Characterization of Connection Assignment of Diagnosable SystemsIEEE Transactions on Computers, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971