A Knowledge Compilation Map
  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.
