Characterization of Diagnosabilities on the Bounded PMC Model

In this paper, we propose a new digragh model for system level fault diagnosis, which is called the (f-1,f {2})-bounded Preparata-Metze-Chien (PMC) model (shortly, (f-1,f {2})-BPMC). The (f-1,f {2})-BPMC model projects a system such that the number of faulty processors that test faulty processors with the test results 0 does not exceed f {2}(f2\leq f {1}) provided that the upper bound on the number of faulty processors is f {1}. This novel testing model compromisingly generalizes PMC model (Preparata, F.P., Metze, G. and Chien R.T. (1967) On the connection assignment problem of diagnosable systems. IEEE Tran. Electron. Comput.,EC-16, 848-854) and Barsi-Grandoni-Maestrini model (Barsi, F., Grandoni, F. and Maestrini, P. (1976) A theory of diagnosability of digital systems. IEEE Trans. Comput.C-25, 585-593). Then we present some characterizations for one-step diagnosibility under the (f-1,f {2})-bounded PMC model, and determine the diagnosabilities of some special regular networks. Meanwhile, we establish the characterizations of f-1/(n-1)-diagnosability and three configurations of f-1/(n-1)-diagnosable system under the (f-1,f {2})-BPMC model.