Preprocessing Boolean Formulae for BDDs in a Probabilistic Context

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2010

Autores

Theofrastos Mantadelis (Autor) Outra; Ricardo Rocha (Autor) FCUP; Angelika Kimmig (Autor) Outra; Gerda Janssens (Autor) Outra

Ata de Conferência Internacional

Título: LOGICS IN ARTIFICIAL INTELLIGENCE, JELIA 2010

Páginas: 260-272

12th European Conference on Logics in Artificial Intelligence (JELIA)

Helsinki, FINLAND, SEP 13-15, 2010

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 4 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

CORDIS: Ciências Físicas > Ciência de computadores

Outras Informações

ID Authenticus: P-007-W2R

DOI: 10.1007/978-3-642-15675-5_23

Abstract (EN): 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Notas: Logics in Artificial Intelligence , Lecture Notes in Computer Science, 2010, Volume 6341/2010, 260-272, Springer-Verlag, DOI: 10.1007/978-3-642-15675-5_23

Nº de páginas: 13