Preprocessing Boolean Formulae for BDDs in a Probabilistic Context
Theofrastos Mantadelis, Ricardo Rocha, Angelika Kimmig and Gerda Janssens
September 2010
Abstract
Inference in many probabilistic logic systems is based on representing
the proofs of a query as a DNF Boolean formula. Assessing the
probability of such a formula is known as a #P-hard task. In
practice, a large DNF is given to a BDD software package to construct
the corresponding BDD. The DNF has to be transformed into the input
format of the package. This is the preprocessing step. In this paper
we investigate and compare different preprocessing methods, including
our new trie based approach. Our experiments within the ProbLog system
show that the behaviour of the methods changes according to the amount
of sharing in the original DNF. The decomposition method is preferred
when there is not much sharing in the DNF, whereas DNFs with sharing
benefit from our trie based method. While our methods are motivated
and applied in the ProbLog context, our results are interesting for
other applications that manipulate DNF Boolean formulae.
Bibtex
@InProceedings{mantadelis-jelia10,
author = {T. Mantadelis, R. Rocha, A. Kimmig and G. Janssens},
title = {{Preprocessing Boolean Formulae for BDDs in a Probabilistic Context}},
booktitle = {Proceedings of the 12th European Conference on Logics in Artificial Intelligence (JELIA 2010)},
pages = {262--274},
number = {6341},
series = {LNAI},
publisher = {Springer},
editor = {T. Janhunen and I. Niemelä},
month = {September},
year = {2010},
address = {Helsinki, Finland},
}
Download Paper
PDF file
Springer