• DocumentCode
    1135874
  • Title

    On the Computational Complexity of System Diagnosis

  • Author

    Fujiwara, Hideo ; Kinoshita, Kozo

  • Author_Institution
    Department of Electronic Engineering, Osaka University
  • Issue
    10
  • fYear
    1978
  • Firstpage
    881
  • Lastpage
    885
  • 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;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/TC.1978.1674966
  • Filename
    1674966
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1135874