{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:25Z","timestamp":1759637965513,"version":"3.37.3"},"reference-count":46,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2019,12,18]],"date-time":"2019-12-18T00:00:00Z","timestamp":1576627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61977016","61572010"],"award-info":[{"award-number":["61977016","61572010"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"publisher","award":["2017J01738","JAT170118","JT180077"],"award-info":[{"award-number":["2017J01738","JAT170118","JT180077"]}],"id":[{"id":"10.13039\/501100003392","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,8,20]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In this paper, we propose a new digragh model for system level fault diagnosis, which is called the $(f_1,f_{2})$-bounded Preparata\u2013Metze\u2013Chien (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}$$(f_2\\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\u2013854) and Barsi\u2013Grandoni\u2013Maestrini model (Barsi, F., Grandoni, F. and Maestrini, P. (1976) A theory of diagnosability of digital systems. IEEE Trans. Comput.C-25, 585\u2013593). 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.<\/jats:p>","DOI":"10.1093\/comjnl\/bxz083","type":"journal-article","created":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T11:27:18Z","timestamp":1564054038000},"page":"1397-1405","source":"Crossref","is-referenced-by-count":6,"title":["Characterization of Diagnosabilities on the Bounded PMC Model"],"prefix":"10.1093","volume":"63","author":[{"given":"Guanqin","family":"Lian","sequence":"first","affiliation":[{"name":"College of Mathematics and Informatics, Fujian Normal University, Fuzhou, Fujian 350117, China"}]},{"given":"Shuming","family":"Zhou","sequence":"additional","affiliation":[{"name":"College of Mathematics and Informatics, Fujian Normal University, Fuzhou, Fujian 350117, China"}]},{"given":"Sun-Yuan","family":"Hsieh","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan 701, Taiwan"}]},{"given":"Gaolin","family":"Chen","sequence":"additional","affiliation":[{"name":"College of Mathematics and Informatics, Fujian Normal University, Fuzhou, Fujian 350117, China"}]},{"given":"Jiafei","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Mathematics and Informatics, Fujian Normal University, Fuzhou, Fujian 350117, China"}]},{"given":"Zhendong","family":"Gu","sequence":"additional","affiliation":[{"name":"College of Mathematics and Informatics, Fujian Normal University, Fuzhou, Fujian 350117, China"}]}],"member":"286","published-online":{"date-parts":[[2019,12,18]]},"reference":[{"key":"2020091506341714600_ref1","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1109\/PGEC.1967.264748","article-title":"On the connection assignment problem of diagnosable systems","volume":"EC-16","author":"Preparata","year":"1967","journal-title":"IEEE Trans. Electron. Comput."},{"key":"2020091506341714600_ref2","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/TC.1976.1674658","article-title":"A theory of diagnosability of digital systems","volume":"C-25","author":"Barsi","year":"1976","journal-title":"IEEE Trans. Comput."},{"key":"2020091506341714600_ref3","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1109\/12.177309","article-title":"On self-diagnosable multiprocessor systems: diagnosis by the comparison approach","volume":"41","author":"Sengupta","year":"1992","journal-title":"IEEE Trans. Comput."},{"key":"2020091506341714600_ref4","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1109\/T-C.1974.223782","article-title":"Characterization of connection assignment of diagnosable systems","volume":"23","author":"Hakimi","year":"1974","journal-title":"IEEE Trans. Comput."},{"key":"2020091506341714600_ref5","first-page":"107","article-title":"Charaeterizalion of (t$^1$\/t$^1\/2$)\/s Diagnosability","volume-title":"Proceedings of the 19th International Symposium on Multiple-Valued Logic","author":"Huang","year":"1989"},{"key":"2020091506341714600_ref6","first-page":"148","article-title":"A polynomial lime algorithm for fault diagnosability","volume-title":"Proceedings of the 25th Annual Symposium on Foundations of Computer Science","author":"Sullivan","year":"1984"},{"key":"2020091506341714600_ref7","first-page":"554","article-title":"Characterization and design of sequentially t-diagnosable systems","volume-title":"Proceedings of the 19th International Symposium on Fault-Tolerant Computing. Digest of Papers","author":"Huang","year":"1989"},{"key":"2020091506341714600_ref8","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1109\/TPDS.2005.44","article-title":"Diagnosabilities of regular networks","volume":"16","author":"Chang","year":"2005","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2020091506341714600_ref9","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/TDSC.2010.59","article-title":"Conditional diagnosability of augmented cubes under the PMC Model","volume":"9","author":"Chang","year":"2012","journal-title":"IEEE Trans. Dependable Secure Comput."},{"key":"2020091506341714600_ref10","doi-asserted-by":"crossref","first-page":"3002","DOI":"10.1109\/TPDS.2013.290","article-title":"Structural properties and conditional diagnosability of star graphs by using the PMC model","volume":"25","author":"Chang","year":"2014","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2020091506341714600_ref11","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1109\/TDSC.2016.2562620","article-title":"Conditional diagnosability of (n;k)-star graphs under the PMC model","volume":"15","author":"Chang","year":"2018","journal-title":"IEEE Trans. Dependable Secure Comput."},{"key":"2020091506341714600_ref12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2504905","article-title":"t\/t-Diagnosability of regular graphs under the PMC model","volume":"18","author":"Chen","year":"2013","journal-title":"ACM Trans. Des. Autom. Electron."},{"key":"2020091506341714600_ref13","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1109\/TC.2005.33","article-title":"The t\/k-diagnosability of the BC graphs","volume":"54","author":"Fan","year":"2005","journal-title":"IEEE Trans. Comput."},{"key":"2020091506341714600_ref14","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1093\/comjnl\/bxx089","article-title":"The 3-extra connectivity and faulty diagnosability","volume":"61","author":"Gu","year":"2018","journal-title":"Comput. J."},{"key":"2020091506341714600_ref15","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1109\/TC.2012.15","article-title":"Conditional diagnosability of alternating group graphs","volume":"62","author":"Hao","year":"2013","journal-title":"IEEE Trans. Comput."},{"key":"2020091506341714600_ref16","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1109\/TPDS.2008.99","article-title":"The strong diagnosability of regular networks and product networks under the PMC model","volume":"20","author":"Hsieh","year":"2009","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"2020091506341714600_ref17","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TC.2005.19","article-title":"Conditional diagnosability measures for large multiprocessor systems","volume":"54","author":"Lai","year":"2005","journal-title":"IEEE Trans. Electron. Comput."},{"key":"2020091506341714600_ref18","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1109\/TDSC.2010.22","article-title":"Determining the diagnosability of (1,2)-matching composition networks and its applications","volume":"8","author":"Lee","year":"2011","journal-title":"IEEE Trans. Depend. Secure Comput."},{"key":"2020091506341714600_ref19","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/j.tcs.2014.10.046","article-title":"Conditional diagnosability and strong diagnosability of Split- Star Networks under the PMC model","volume":"562","author":"Lin","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"2020091506341714600_ref20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2017.11.004","article-title":"The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model","volume":"95","author":"Lin","year":"2018","journal-title":"J. Comput. Syst. Sci."},{"key":"2020091506341714600_ref21","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1142\/S0219265908002175","article-title":"Conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model","volume":"9","author":"Lin","year":"2008","journal-title":"J. Int. Net."},{"key":"2020091506341714600_ref22","first-page":"494","article-title":"The g-good-neighbor conditional diagnosability of hypercube under PMC model","volume":"218","author":"Peng","year":"2010","journal-title":"Appl. Math. Comput."},{"key":"2020091506341714600_ref23","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.tcs.2012.05.015","article-title":"A general technique to establish the asymptotic conditional diagnosability of interconnection networks","volume":"452","author":"Stewart","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"2020091506341714600_ref24","doi-asserted-by":"crossref","first-page":"1839","DOI":"10.1093\/comjnl\/bxw037","article-title":"The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks","volume":"59","author":"Wang","year":"2016","journal-title":"Comput. J."},{"key":"2020091506341714600_ref25","first-page":"241","article-title":"The 2-good-neighbor (2-extra) diagnosability of alternating group graph networks under the PMC model and MM$^{\\ast }$ model","volume":"305","author":"Wang","year":"2017","journal-title":"Appl. Math. Comput."},{"key":"2020091506341714600_ref26","first-page":"875","article-title":"Conditional diagnosability of matching composition networks under the PMC model. IEEE Trans. Circuits Syst. II, Exp","volume":"56","author":"Xu","year":"2009","journal-title":"Briefs"},{"key":"2020091506341714600_ref27","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1016\/j.ipl.2012.06.008","article-title":"On deriving conditional diagnosability of interconnection networks","volume":"112","author":"Cheng","year":"2012","journal-title":"Inf. Process. Lett."},{"key":"2020091506341714600_ref28","doi-asserted-by":"crossref","first-page":"2275","DOI":"10.1080\/00207160.2010.544723","article-title":"Conditional diagnosability of hypermesh optical multiprocessor systems under the PMC model","volume":"88","author":"Yang","year":"2011","journal-title":"Int. J. Comput. Math."},{"key":"2020091506341714600_ref29","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1109\/TPDS.2014.2318305","article-title":"The g-good-neighbor conditional diagnosability of $k$-ary $n$-cubes under the PMC model and MM$^{\\ast }$ model","volume":"26","author":"Yuan","year":"2015","journal-title":"IEEE Trans. Parallel Distr. Syst."},{"key":"2020091506341714600_ref30","doi-asserted-by":"crossref","first-page":"1847","DOI":"10.1109\/TC.2013.64","article-title":"Relating diagnosability, strong diagnosability and conditional diagnosability of strong networks","volume":"63","author":"Zhu","year":"2014","journal-title":"IEEE Trans. Comput."},{"key":"2020091506341714600_ref31","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1016\/j.ins.2012.08.014","article-title":"Conditional diagnosability of balanced hypercubes under the PMC model","volume":"222","author":"Yang","year":"2013","journal-title":"Inf. Sci."},{"key":"2020091506341714600_ref32","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2017.02.011","article-title":"The g-good-neighbor conditional diagnosability of star graphs under the PMC and MM$^{\\ast }$ model","volume":"674","author":"Li","journal-title":"Theor. Comput. Sci."},{"key":"2020091506341714600_ref33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2018.07.019","article-title":"Hybrid fault diagnosis capability analysis of hypercubes under the PMC model and MM$^{\\ast }$ model","volume":"758","author":"Zhu","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"2020091506341714600_ref34","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.ins.2011.10.022","article-title":"A fast fault-identification algorithm for bijective connection graphs using the PMC model","volume":"187","author":"Li","year":"2012","journal-title":"Inf. Sci."},{"key":"2020091506341714600_ref35","first-page":"613","article-title":"A test round controllable local diagnosis algorithm under the PMC diagnosis model","volume":"244","author":"Teng","year":"2014","journal-title":"Appl. Math. Comput."},{"key":"2020091506341714600_ref36","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1109\/TC.2013.228","article-title":"The t\/k-diagnosability of star graph network","volume":"62","author":"Zhou","year":"2015","journal-title":"IEEE Trans. Comput."},{"key":"2020091506341714600_ref37","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1016\/j.jpdc.2004.02.002","article-title":"A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems","volume":"64","author":"Yang","year":"2004","journal-title":"J. Parallel Distr. Comput."},{"key":"2020091506341714600_ref38","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/S0019-9958(81)90388-0","article-title":"Schemes for fault tolerant computing: a comparison of modularly redundant and t-diagnosable systems","volume":"49","author":"Chwa","year":"1981","journal-title":"Inf. Control"},{"key":"2020091506341714600_ref39","first-page":"545","article-title":"On diagnosable systems with simple algorithms","volume-title":"Proceedings of the 1980 Conference on Information Science and Systems","author":"Mallela","year":"1980"},{"article-title":"Comparison-based diagnosis in fault-tolerant, multiprocessor systems. Ph.D. Dissertation","year":"1996","author":"Fuhrman","key":"2020091506341714600_ref40"},{"key":"2020091506341714600_ref41","first-page":"395","article-title":"A class of 2-step diagnosable systems: degree off diagnosabilityand a diagnosis algorithm","volume":"1","author":"Huang","year":"1992","journal-title":"IEEE Int. Symp. Circuits Syst."},{"key":"2020091506341714600_ref42","first-page":"167","article-title":"A new measure of digital system diagnosis","author":"Friedman","year":"1975","journal-title":"Proceedings of the 5th International Symposium on Fault-Tolerant Computing"},{"key":"2020091506341714600_ref43","first-page":"496","article-title":"The t\/(n-1) diagnosability and its applications to fault tolerance","volume-title":"Proceedings of the 21st International Symposium on Fault-Tolerant Computing","author":"Xu","year":"1991"},{"key":"2020091506341714600_ref44","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1016\/0165-6074(90)90308-V","article-title":"A new comparison-based scheme for multiprocessor fault tolerance","volume":"30","author":"Xu","year":"1990","journal-title":"Microprocess. Microprogramm."},{"volume-title":"Combinational Theory in Networks","year":"2013","author":"Xu","key":"2020091506341714600_ref45"},{"key":"2020091506341714600_ref46","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1002\/net.21539","article-title":"Generalized measures for fault tolerance of star networks","volume":"63","author":"Li","year":"2014","journal-title":"Networks"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/9\/1397\/33747623\/bxz083.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/63\/9\/1397\/33747623\/bxz083.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T10:38:14Z","timestamp":1600166294000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/63\/9\/1397\/5680451"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,18]]},"references-count":46,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,12,18]]},"published-print":{"date-parts":[[2020,8,20]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxz083","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2020,9]]},"published":{"date-parts":[[2019,12,18]]}}}