Introduction
Knowledge Compilation (KC) serves as a fundamental strategy in Artificial Intelligence for managing computationally intensive tasks. By translating complex logical theories into "compiled" formats during an offline phase, researchers can ensure that subsequent queries—such as consistency checks or variable forgetting—are resolvable in polynomial time.
In 2002, Darwiche and Marquis established a landmark "Knowledge Compilation Map," comparing formats like Ordered Binary Decision Diagrams (OBDDs), Disjunctive Normal Form (DNF), and Decomposable Negation Normal Form (DNNF) based on their succinctness and tractability. However, this map omitted several classical propositional logic fragments. This paper extends that framework by incorporating ten new fragments based on Krom, Horn, and Affine logics, exploring their potential as efficient target languages for compilation.
Methodology
The authors define ten propositional fragments, categorized into "incomplete" and "complete" versions. The incomplete fragments, which cannot represent every logical theory, include:
- KROM-C (bijunctive)
- HORN-C
- K/H-C (Krom or Horn)
- renH-C (renamable Horn)
- AFF (affine/biconditional)
To achieve full expressiveness, the authors analyze five "complete" versions formed by taking disjunctions of these fragments (e.g., HORN-C[∨]). The study is purely theoretical, utilizing mathematical proofs to determine the polynomial-time feasibility of standard queries (e.g., Consistency, Model Counting) and transformations (e.g., Conditioning, Forgetting, Conjunction).
Key Insights and the Succinctness Hierarchy
A primary contribution of this work is the establishment of a new succinctness ordering. The authors demonstrate that fragments like renH-C[∨] (renamable Horn disjunctions) are strictly more succinct than standard Horn or Krom disjunctions.
One of the most significant findings involves the power of bounded conjunction ($\wedge BC$). While the popular DNNF format is highly succinct, it fails to support efficient bounded conjunction. In contrast, fragments such as HORN-C[∨] and AFF[∨] allow for efficient joining of compiled components, making them superior for systems built incrementally.
Tractability and Transformation Results
The research identifies that all ten fragments support polynomial-time Clausal Entailment (CE) and Conditioning (CD). The AFF[∨] fragment is particularly noteworthy as it satisfies both Forgetting (FO) and Conjunction ($\wedge C$), a combination not found even in OBDDs.
The complete fragments AFF[∨], HORN-C[∨], and KROM-C[∨] emerge as compelling alternatives to DNNF due to their support for the $\wedge BC$ transformation. While these fragments are strictly more succinct than DNF, their exact relationship to DNNF remains an open question, though the authors conjecture they may be incomparable.
Conclusion
This extension of the Knowledge Compilation Map provides a more comprehensive landscape for choosing target languages in AI applications. While the theoretical groundwork for efficient operations is now established, future work is needed to develop optimized compilation algorithms, particularly for the AFF[∨] fragment, and to formally resolve the succinctness relationship between these new fragments and DNNF.
Summary updated