Compiling Knowledge into Decomposable Negation Normal Form

Adnan Darwiche

Abstract

We propose a method for compiling propositional theories into a new tractable form that we refer to as decomposable negation normal form (DNNF). We show a number of results about our compilation approach. First, we show that every propositional theory can be compiled into DNNF and present an algorithm to this effect. Second, we show that if a clausal form has a bounded treewidth, then its DNNF compilation has a linear size and can be computed in linear time - treewidth is a graphtheoretic parameter which measures the connectivity of the clausal form. Third, we show that once a propositional theory is compiled into DNNF, a number of reasoning tasks, such as satisfiability and forgetting, can be performed in linear time. Finally, we propose two techniques for approximating the DNNF compilation of a theory when the size of such compilation is too large to be practical. One of the techniques generates a sound but incomplete compilation, while the other generates a complete but unsound compilation. Together, these approximations bound the exact compilation from below and above in terms for their ability to answer queries.

Introduction

In artificial intelligence, automated reasoning often faces a "pay-as-you-go" computational challenge. Standard tasks like checking the satisfiability of a set of constraints are NP-complete, requiring significant resources for every query. Knowledge Compilation addresses this by performing intensive computation upfront to transform a logical theory into a "tractable" form. Once compiled, answering queries becomes significantly more efficient.

While previous efforts focused on formats like Horn theories, they often suffered from loss of information. This work introduces Decomposable Negation Normal Form (DNNF), a representation that is both universal—capable of representing any propositional theory—and tractable for a wide range of reasoning tasks.

Decomposable Negation Normal Form (DNNF)

DNNF is a subset of Negation Normal Form (NNF) characterized by the decomposability property. In a DNNF, for any conjunction (AND gate), the sub-theories represented by its children must involve disjoint sets of variables (atoms). This property is the key to ensuring that complex operations can be decomposed into independent, simpler sub-problems.

Example of a DNNF structure showing the decomposability property where AND gates operate on disjoint sets of atoms.

Compilation Methodology

The paper introduces recursive algorithms, DNNF1 and DNNF2, to perform this compilation. These procedures utilize case analysis, similar to Shannon expansion, to break down a theory into independent components.

A critical component of this process is the use of Decomposition Trees. By partitioning the clauses of a theory into a tree structure, the algorithm can systematically manage the complexity of the transformation. Furthermore, caching is employed to store the results of sub-problems, preventing redundant work and significantly speeding up the compilation of repetitive logical structures.

A decomposition tree used to guide the recursive partitioning of a logical theory during compilation.

Theoretical Insights and Results

The research establishes several key properties of DNNF:

  • Linear-Time Reasoning: Once a theory is in DNNF, tasks such as checking satisfiability or "forgetting" a variable (existential quantification) can be solved in $O(n)$ time, where $n$ is the size of the DNNF.
  • Treewidth and Complexity: The complexity of compiling a theory is governed by its treewidth—a graph-theoretic measure of connectivity. If a theory has a bounded treewidth $w$, its DNNF compilation has a linear size $O(n \cdot 2^w)$ and can be computed in linear time.
  • Compactness: For certain functions, such as the odd-parity function, DNNF provides an exponentially more compact representation than traditional formats like Disjunctive Normal Form (DNF).

Approximations and Limitations

For theories with high treewidth where exact compilation is computationally prohibitive, the paper proposes two approximation techniques: $DNNF_u$ (sound but incomplete) and $DNNF_l$ (complete but unsound). These provide upper and lower bounds for answering queries.

The primary limitation remains the exponential dependence on treewidth during the initial compilation phase. While DNNF is powerful, highly "tangled" logical theories may still result in representations that are too large for practical use. Future work involves developing optimized heuristics for variable selection during approximation and industrial-strength compiler implementations.

Summary updated

Abstract

We propose a method for compiling propositional theories into a new tractable form that we refer to as decomposable negation normal form (DNNF). We show a number of results about our compilation approach. First, we show that every propositional theory can be compiled into DNNF and present an algorithm to this effect. Second, we show that if a clausal form has a bounded treewidth, then its DNNF compilation has a linear size and can be computed in linear time - treewidth is a graphtheoretic parameter which measures the connectivity of the clausal form. Third, we show that once a propositional theory is compiled into DNNF, a number of reasoning tasks, such as satisfiability and forgetting, can be performed in linear time. Finally, we propose two techniques for approximating the DNNF compilation of a theory when the size of such compilation is too large to be practical. One of the techniques generates a sound but incomplete compilation, while the other generates a complete but unsound compilation. Together, these approximations bound the exact compilation from below and above in terms for their ability to answer queries.
BibTeX
@inproceedings{darwiche1999compiling,
  author = {Adnan Darwiche},
  title = {{Compiling Knowledge into Decomposable Negation Normal Form}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure