A Knowledge Compilation Map

By Adnan Darwiche, Pierre Marquis. 2002

1,046 citations recorded by the source corpus.

We propose a perspective on knowledge compilation which calls for analyzing different compilation approaches according to two key dimensions: the succinctness of the target compilation language, and the class of queries and transformations that the language supports in polytime. We then provide a knowledge compilation map, which analyzes a large number of existing target compilation languages according to their succinctness and their polytime transformations and queries. We argue that such analysis is necessary for placing new compilation approaches within the context of existing ones. We also go beyond classical, flat target compilation languages based on CNF and DNF, and consider a richer, nested class based on directed acyclic graphs (such as OBDDs), which we show to include a relatively large number of target compilation languages.

Subfields: Artificial Intelligence, Computer Networks and Communications, Software

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Software

Citations in the corpus

DeepProbLog: Neural Probabilistic Logic Programming (2018, methodology): “(iii) The third step compiles the logic formula into a Sentential Decision Diagram (SDD, Darwiche [2011]), a form that allows for efﬁcient evaluation of the query, using knowledge compilation technology [Darwiche and Marquis, 2002].”
Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting (2019, methodology): “Following compilation, exact inference in WMC can be done in linear time (Darwiche and Marquis 2002).”
Compiling Combinatorial Prediction Games (2018, methodology): “Namely, any OBDD can be transformed in linear time and space into an equivalent dDNNF circuit, but the converse is not true: dDNNF includes simple circuits which require an exponential size representation in OBDD.”
A Semantic Loss Function for Deep Learning with Symbolic Knowledge (2017, methodology): “We use the language and circuit compilation techinques described in Darwiche (2011) to build a Boolean circuit representing (Darwiche & Marquis, 2002).”
Three Modern Roles for Logic in AI (2020, background): “NNF circuits are not tractable, but they become tractable once we impose certain properties on them [34].”
An Algebraic Prolog for Reasoning about Possible Worlds (2011, neutral): “This idea is closely related to the concept of a smooth NNF circuit used in knowledge compilation, where operands of a disjunction use the same set of variables (Darwiche and Marquis 2002).”
A differential approach to inference in Bayesian networks (2000, background): “If 3 Note that an Ordered Binary Decision Diagram (OBDD) can be understood as a Boolean circuit, in which case it can be shown to be an NNF that satis.es the properties of decomposability and determinism [Bryant 1986; Darwiche and Marquis 2002].”
Probabilistic Logical Inference on the Web (2016, background): “This problem is difficult (#P complexity) but converting the DNF into a language from which the computation of the probability is polynomial (knowledge compilation [1]) yields algorithm able to handle problems of significant size [2,16].”
On the Tractability of SHAP Explanations (2020, background): “Expectations can be computed in time linear in the size of various circuit representations, called d-DNNF, which includes binary decision diagrams (OBDD, FBDD) and SDDs (Bryant 1986; Darwiche and Marquis 2002).”