{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T18:58:54Z","timestamp":1767985134589,"version":"3.49.0"},"reference-count":0,"publisher":"AI Access Foundation","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["jair"],"abstract":"<jats:p>We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.<\/jats:p>","DOI":"10.1613\/jair.3025","type":"journal-article","created":{"date-parts":[[2018,7,17]],"date-time":"2018-07-17T10:35:57Z","timestamp":1531823757000},"page":"371-413","source":"Crossref","is-referenced-by-count":27,"title":["Approximate Model-Based Diagnosis Using Greedy Stochastic Search"],"prefix":"10.1613","volume":"38","author":[{"given":"A.","family":"Feldman","sequence":"first","affiliation":[]},{"given":"G.","family":"Provan","sequence":"additional","affiliation":[]},{"given":"A.","family":"Van Gemund","sequence":"additional","affiliation":[]}],"member":"16860","published-online":{"date-parts":[[2010,7,27]]},"container-title":["Journal of Artificial Intelligence Research"],"original-title":[],"link":[{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10657\/25475","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10657\/25474","content-type":"application\/postscript","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/download\/10657\/25475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,20]],"date-time":"2019-10-20T18:26:39Z","timestamp":1571595999000},"score":1,"resource":{"primary":{"URL":"https:\/\/jair.org\/index.php\/jair\/article\/view\/10657"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,27]]},"references-count":0,"URL":"https:\/\/doi.org\/10.1613\/jair.3025","relation":{"cites":[{"id-type":"doi","id":"10.3390\/s18041016","asserted-by":"object"}]},"ISSN":["1076-9757"],"issn-type":[{"value":"1076-9757","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,27]]}}}