Using Quine-McCluskey algorithm to improve the compiling of possibilitic networks

Compiling Possibilistic Networks consists in evaluating the effect of evidence by encoding the possibilistic network in the form of a multivariable function. This function can be factored and represented by a graph which allows the calculation of new conditional possibilities. Encoding the possibilistic network using a formula in the Conjunctive Normal Form (CNF) makes it possible to factorize the multivariable function and generate a deterministic graph in a Decomposable Negative Normal Form (d-DNNF) whose computation time is polynomial. The challenge of compiling possibilistic networks is to minimize the number of clauses and the size of the d-DNNF graph in order to guarantee the lowest possible computation time. Several solutions exist to reduce the number of CNF clauses.We present in this paper the possible improvements for the encoding of possibilistic networks. We will then focus on the use of Quine- McCluskey’s algorithm (QMC) to simplify and reduce the number of clauses.