Algebraic model counting

Kimmig, Angelika ORCID: https://orcid.org/0000-0002-6742-4057, Van den Broeck, Guy and De Raedt, Luc 2017. Algebraic model counting. Journal of Applied Logic 22 , pp. 46-62. 10.1016/j.jal.2016.11.031

Preview

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (442kB) | Preview

Abstract

Weighted model counting (WMC) is a well-known inference task on knowledge bases, and the basis for some of the most efficient techniques for probabilistic inference in graphical models. We introduce algebraic model counting (AMC), a generalization of WMC to a semiring structure that provides a unified view on a range of tasks and existing results. We show that AMC generalizes many well-known tasks in a variety of domains such as probabilistic inference, soft constraints and network and database analysis. Furthermore, we investigate AMC from a knowledge compilation perspective and show that all AMC tasks can be evaluated using sd-DNNF circuits, which are strictly more succinct, and thus more efficient to evaluate, than direct representations of sets of models. We identify further characteristics of AMC instances that allow for evaluation on even more succinct circuits.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	Elsevier
ISSN:	1570-8683
Date of First Compliant Deposit:	20 November 2017
Date of Acceptance:	7 July 2016
Last Modified:	30 Nov 2024 04:00
URI:	https://orca.cardiff.ac.uk/id/eprint/106735

Citation Data

Cited 25 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item