Title :
On the Computational Complexity of System Diagnosis
Author :
Fujiwara, Hideo ; Kinoshita, Kozo
Author_Institution :
Department of Electronic Engineering, Osaka University
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 :
Fault diagnosis; Turing machines; polynomial time algorithm; polynomially complete; self-diagnosable systems; Availability; Computational complexity; Digital systems; Fault diagnosis; Polynomials; Sufficient conditions; System testing; Traveling salesman problems; Turing machines; Fault diagnosis; Turing machines; polynomial time algorithm; polynomially complete; self-diagnosable systems;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1978.1674966
