A generalization of the algorithm of Heidtmann to non-monotone formulas

✍ Scribed by R. Bertschy; P.A. Monney

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 993 KB
• Volume: 76
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/s0377-0427(96)00089-1

✦ Synopsis

The following problem from reliability theory is considered. Given a disjunctive normal form (DNF) ~0 = ~ol v ... v ~or, we want to find a representation of ~0 into disjoint formulas, i.e. find formulas th,..., qs such that q~ = ql v .-. v q~ and t/i/x r b = _1_ whenever i ¢j. In addition, the formulas ~1 ..... qs must be simple enough that the computation of their probabilities is a simple task. Of course, it is also better if there is only a small number of formulas qi in the representation. It has recently been discovered that this problem also appears in the calculation of degrees of support in the context of probabilistic assumption-based reasoning and the Dempster-Shafer theory of evidence . In this paper we present a new method to solve this problem, where each formula t h is a so-called mix-product. Our method can be applied to any DNF, not only to monotone ones like the method of Heidtmann (1989). However, when applied to monotone formulas, both methods generate the same results. Compared to the algorithm of which can also be applied to any DNF, our method is considerably more efficient and will generate a much smaller number of disjoint terms in most cases (see Section 5).