Issue No.10 - October (1978 vol.27)
H. Fujiwara , Department of Electronic Engineering, Osaka University
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.
Turing machines, Fault diagnosis, polynomial time algorithm, polynomially complete, self-diagnosable systems
H. Fujiwara, K. Kinoshita, "On the Computational Complexity of System Diagnosis", IEEE Transactions on Computers, vol.27, no. 10, pp. 881-885, October 1978, doi:10.1109/TC.1978.1674966