# A Knowledge Compilation Map

Adnan Darwiche **darwiche@cs.ucla.edu**
Computer Science Department University of California, Los Angeles Los Angeles, CA 90095, USA
Pierre Marquis **marquis@cril.univ-artois.fr**
Universit´e d'Artois F-62307, Lens Cedex, France

## Abstract

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.**

## 1. Introduction

Knowledge compilation has emerged recently as a key direction of research for dealing **with the** computational intractability of general propositional reasoning (Darwiche, 1999; Cadoli & Donini, 1997; Boufkhad, Gr´egoire, Marquis, Mazure, & Sa¨ıs, 1997; Khardon & Roth, 1997; Selman &
Kautz, 1996; Schrag, 1996; Marquis, 1995; del Val, 1994; Dechter & Rish, 1994; Reiter & de Kleer, 1987). According to this direction, a propositional theory is compiled off-line into a target language, which is then used on-line to answer a large number of queries in polytime. The key motivation behind knowledge compilation is to push as much of the computational overhead into the off-line phase, which is amortized over all on-line queries. But knowledge compilation can serve other important purposes as well. For example, target compilation languages **and their associated** algorithms can be very simple, allowing one to develop on-line reasoning systems for simple software and hardware platforms. Moreover, the simplicity of algorithms that operate on compiled languages help in streamlining the effort of algorithmic design into a single task: that of generating the smallest compiled representations possible, as that turns out to be the main computational **bottleneck in**
compilation approaches.

There are three key aspects of any knowledge compilation approach: the succinctness of the target language into which the propositional theory is compiled; the class of **queries that can be**
answered in polytime based on the compiled representation; and the class of transformations that can be applied to the representation in polytime. The AI literature has thus far focused mostly on target compilation languages which are variations on DNF and CNF formulas, such as Horn theories and prime implicates. Moreover, it has focused mostly on clausal entailment queries, with very little discussion of tractable transformations on compiled theories.

The goal of this paper is to provide a broad perspective on knowledge compilation by considering a relatively large number of target compilation languages and analyzing them according to their succinctness and the class of queries/transformations **that they admit in polytime.**
°c 2002 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.