<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>47</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Rui Abreu</style></author><author><style face="normal" font="default" size="100%">Van Gemund, Arjan JC</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Statistics-directed Minimal Hitting Set Algorithm</style></title><secondary-title><style face="normal" font="default" size="100%">Proceedings of the Twentieth International Workshop on Principles of Diagnosis (DX'09)</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2009</style></year><pub-dates><date><style  face="normal" font="default" size="100%">June</style></date></pub-dates></dates><urls><related-urls><url><style face="normal" font="default" size="100%">https://haslab.uminho.pt/sites/default/files/ruimaranhao/files/sara09.pdf</style></url></related-urls></urls><pub-location><style face="normal" font="default" size="100%">Stockholm, Sweden</style></pub-location><pages><style face="normal" font="default" size="100%">51–58</style></pages><language><style face="normal" font="default" size="100%">eng</style></language><abstract><style face="normal" font="default" size="100%">&lt;p&gt;Generating minimal hitting sets of a collection of sets is known to be NP-hard, necessitating heuristic approaches to handle large problems. In this paper a low-cost, approximate minimal hitting set (MHS) algorithm, coined Staccato, is presented. Staccato uses a heuristic function, borrowed from a lightweight, statistics-based software fault localization approach, to guide the MHS search. Given the nature of the heuristic function, Staccato is specially tailored to model-based diagnosis problems (where each MHS solution is a diagnosis to the problem), although well-suited for other application domains as well. We apply Staccato in the context of model-based diagnosis and show that even for small problems our approach is orders of magnitude faster than the brute-force approach, while still capturing all important solutions. Furthermore, due to its low cost complexity, we also show that Staccato is amenable to large problems including millions of variables.&lt;/p&gt;
</style></abstract></record></records></xml>