A Deletion Algorithm for the Marginal Problem in Propositional Logic Based on Boolean Arrays

Efraín Díaz-Macías () and Serafín Moral
Additional contact information
Efraín Díaz-Macías: Faculty of Engineering Sciences, State Technical University of Quevedo, Quevedo 120301, Ecuador
Serafín Moral: Department of Computer Science and Artificial Intelligence, University of Granada, 18071 Granada, Spain

Mathematics, 2023, vol. 11, issue 12, 1-28

Abstract: This paper proposes a deletion algorithm for the marginal problem in propositional logic. The algorithm is based on the general Davis and Putnam deletion algorithm DP, expressed as a bucket elimination algorithm, representing sets of clauses with the same set of variables employing a Boolean array. The main contribution is the development of alternative procedures when deleting a variable which allow more efficient computations. In particular, it takes advantage of the case in which the variable to delete is determined by a subset of the rest of the variables. It also provides a set of useful results and tools for reasoning with Boolean tables. The algorithms are implemented using Python and the NumPy library. Experiments show that this procedure is feasible for intermediate problems and for difficult problems from hard Bayesian networks cases

Keywords: marginal problem; satisfiability problem; propositional logic; propagation algorithm; calculus with potentials (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/12/2748/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/12/2748/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:12:p:2748-:d:1173469

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().