In general, the best explanation for a given observation makes no promises on how good it is with respect to other alternative explanations. A major deficiency of message-passing schemes for belief revision in Bayesian networks is their inability to generate alternatives beyond the second best. In this paper, we present a general approach based on linear constraint systems that naturally generates alternative explanations in an orderly and highly efficient manner. This approach is then applied to cost-based abduction problems as well as belief revision in Bayesian net works.

You happen to know that Tim and Harry have recently had a terrible row that ended their friendship. Now someone tells you that she just saw Tim and Harry jogging together. The best explanation for this that you can think of is that they made up. You conclude that they are friends again. One morning you enter the kitchen to find a plate and cup on the table, with breadcrumbs and a pat of butter on it, and surrounded by a jar of jam, a pack of sugar, and an empty carton of milk. You conclude that one of your house-mates got up at night to make him- or herself a midnight snack and was too tired to clear the table. This, you think, best explains the scene you are facing. To be sure, it might be that someone burgled the house and took the time to have a bite while on the job, or a house-mate might have arranged the things on the table without having a midnight snack but just to make you believe that someone had a midnight snack. But these hypotheses strike you as providing much more contrived explanations of the data than the one you infer to. Walking along the beach, you see what looks like a picture of Winston Churchill in the sand. It could be that, as in the opening pages of Hilary Putnam's (1981), what you see is actually the trace of an ant crawling on the beach. The much simpler, and therefore (you think) much better, explanation is that someone intentionally drew a picture of Churchill in the sand. That, in any case, is what you come away believing. In these examples, the conclusions do not follow logically from the premises.

Bobbio, Andrea, Montani, Stefania, Portinale, Luigi

Dependability modeling and evaluation is aimed at investigating that a system performs its function correctly in time. A usual way to achieve a high reliability, is to design redundant systems that contain several replicas of the same subsystem or component. State space methods for dependability analysis may suffer of the state space explosion problem in such a kind of situation. Combinatorial models, on the other hand, require the simplified assumption of statistical independence; however, in case of redundant systems, this does not guarantee a reduced number of modeled elements. In order to provide a more compact system representation, parametric system modeling has been investigated in the literature, in such a way that a set of replicas of a given subsystem is parameterized so that only one representative instance is explicitly included. While modeling aspects can be suitably addressed by these approaches, analytical tools working on parametric characterizations are often more difficult to be defined and the standard approach is to 'unfold' the parametric model, in order to exploit standard analysis algorithms working at the unfolded 'ground' level. Moreover, parameterized combinatorial methods still require the statistical independence assumption. In the present paper we consider the formalism of Parametric Fault Tree (PFT) and we show how it can be related to Probabilistic Horn Abduction (PHA). Since PHA is a framework where both modeling and analysis can be performed in a restricted first-order language, we aim at showing that converting a PFT into a PHA knowledge base will allow an approach to dependability analysis directly exploiting parametric representation. We will show that classical qualitative and quantitative dependability measures can be characterized within PHA. Furthermore, additional modeling aspects (such as noisy gates and local dependencies) as well as additional reliability measures (such as posterior probability analysis) can be naturally addressed by this conversion. A simple example of a multi-processor system with several replicated units is used to illustrate the approach.