Compacting boolean formulae for inference in probabilistic logic programming

Theofrastos Mantadelis*, Dimitar Shterionov, Gerda Janssens

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)


Knowledge compilation converts Boolean formulae for which some inference tasks are computationally expensive into a representation where the same tasks are tractable. ProbLog is a state-of-the-art Probabilistic Logic Programming system that uses knowledge compilation to reduce the expensive probabilistic inference to an efficient weighted model counting. Motivated to improve ProbLog’s performance we present an approach that optimizes Boolean formulae in order to speed-up knowledge compilation. We identify 7 Boolean subformulae patterns that can be used to re-write Boolean formulae.We implemented an algorithm with polynomial complexity which detects and compacts 6 of these patterns. We employ our method in the inference pipeline of ProbLog and conduct extensive experiments. We show that our compaction method improves knowledge compilation and consecutively the overall inference performance. Furthermore, using compaction reduces the number of time-outs, allowing us to solve previously unsolvable problems.

Original languageEnglish
Title of host publicationLogic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Proceedings
EditorsMiroslaw Truszczynski, Francesco Calimeri, Giovambattista Ianni
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783319232638
Publication statusPublished - 2015
Externally publishedYes
Event13th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2015 - Lexington, United States
Duration: 27 Sept 201530 Sept 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference13th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2015
Country/TerritoryUnited States


Dive into the research topics of 'Compacting boolean formulae for inference in probabilistic logic programming'. Together they form a unique fingerprint.

Cite this