Compilation of Propositional Weighted Bases
  In this paper, we investigate the extent to which knowledge compilation can
be used to improve inference from propositional weighted bases. We present a
general notion of compilation of a weighted base that is parametrized by any
equivalence--preserving compilation function. Both negative and positive
results are presented. On the one hand, complexity results are identified,
showing that the inference problem from a compiled weighted base is as
difficult as in the general case, when the prime implicates, Horn cover or
renamable Horn cover classes are targeted. On the other hand, we show that the
inference problem becomes tractable whenever DNNF-compilations are used and
clausal queries are considered. Moreover, we show that the set of all preferred
models of a DNNF-compilation of a weighted base can be computed in time
polynomial in the output size. Finally, we sketch how our results can be used
in model-based diagnosis in order to compute the most probable diagnoses of a
system.
