Extending the Knowledge Compilation Map: Krom, Horn, Affine and Beyond

Hélène Fargier, Pierre MarquisAAAI 2008

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.

Figure 1: The extended Knowledge Compilation Map showing the succinctness relationships between various propositional fragments.

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.

Figure 3: Tractability of transformations across the new propositional fragments. Checkmarks indicate polynomial-time feasibility.

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

BibTeX
@inproceedings{fargier2008extending,
  author = {Hélène Fargier and Pierre Marquis},
  title = {{Extending the Knowledge Compilation Map: Krom, Horn, Affine and Beyond}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure