TL;DR
This paper introduces Decomposable Negation Normal Form (DNNF), a new, tractable representation for propositional theories. They provide an algorithm to compile any propositional theory into DNNF, enabling efficient reasoning tasks like satisfiability and entailment in linear time, especially when the input theory has a bounded treewidth.
What Problem Does This Paper Address?
Automated reasoning systems often struggle with the computational complexity of large propositional theories. A common strategy is to "compile" these theories into a more tractable form during an "off-line" phase, allowing for faster query answering in an "on-line" phase. Existing compilation methods, like compiling into Horn theories, have limitations: not all theories can be compiled this way, and approximations can be complex. This paper aims to provide a more general and efficient compilation technique that can handle any propositional theory and offers a more robust framework for reasoning.
Methods
The core contribution is the introduction of Decomposable Negation Normal Form (DNNF). DNNF is a generalization of Disjunctive Normal Form (DNF) and a specialization of Negation Normal Form (NNF). Its key property is "decomposability": for any conjunction within the DNNF, its constituent parts do not share any atoms. This property makes reasoning tasks like satisfiability decidable in linear time.
The authors present an algorithm (DNNF1 and its optimized version DNNF2) to compile any propositional theory into DNNF. This compilation process leverages decomposition trees, which recursively partition the clauses of a theory. The efficiency of this compilation is strongly linked to the treewidth of the theory's interaction graph. If the treewidth is bounded, the compilation is linear in time and space.
For cases where the exact DNNF compilation is too large, they propose two approximation techniques:
- DNNFu (Ignoring Atoms): This method compromises decomposability but preserves equivalence. It generates sound but potentially incomplete compilations.
- DNNFI (Ignoring Instantiations): This method preserves decomposability but can strengthen the theory. It generates complete but potentially unsound compilations.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- DNNF as a Universal and Tractable Form: The paper demonstrates that any propositional theory can be compiled into DNNF, unlike some prior methods. Crucially, DNNF allows for linear-time satisfiability and entailment checks, a significant efficiency gain.
- Treewidth is Key to Efficient Compilation: The paper establishes a strong connection between the treewidth of a theory's interaction graph and the efficiency of its DNNF compilation. Theories with bounded treewidth can be compiled efficiently (linearly), highlighting the importance of graph-theoretic properties in knowledge representation.
- Approximations for Practicality: The introduction of DNNFu and DNNFI provides practical solutions for handling theories that would otherwise lead to intractably large DNNF compilations. These approximations offer a trade-off between soundness, completeness, and decomposability, bounding the exact compilation from below and above.
- Forgetting Atoms is Efficient in DNNF: Once a theory is in DNNF, the operation of "forgetting" (removing atoms from consideration) can be performed in linear time. This has applications in simplifying representations and computing implications.
Key Results
- Every propositional theory can be compiled into DNNF.
- If a clausal form has a bounded treewidth, its DNNF compilation is linear in size and can be computed in linear time.
- Reasoning tasks (satisfiability, forgetting, entailment) on DNNF representations can be performed in linear time.
- The paper provides two approximation techniques (DNNFu and DNNFI) that offer sound but incomplete, or complete but unsound, DNNF compilations, respectively.
Limitations and Future Work
- Heuristic Nature of Approximations: The paper acknowledges that the choice of which atoms to ignore (for DNNFu) or which instantiations to consider (for DNNFI) is typically heuristic and not addressed in detail. Future work could explore more principled methods for these choices.
- Construction of Good Decomposition Trees: While the paper links efficient compilation to bounded treewidth, the practical construction of optimal decomposition trees (or jointrees) for arbitrary theories remains an area for further research.
- Comparison with BDDs: The paper mentions comparing DNNFs with Binary Decision Diagrams (BDDs) in an appendix (not provided in the excerpt), suggesting this is an area for further exploration.
Summary updated