A Knowledge Compilation Map

A Knowledge Compilation Map

2002 | Adnan Darwiche, Pierre Marquis
This paper presents a knowledge compilation map that analyzes various target compilation languages based on two key dimensions: the succinctness of the language and the class of queries and transformations it supports in polytime. The authors propose a richer, nested class of target compilation languages based on directed acyclic graphs (DAGs), such as OBDDs, which includes many existing languages. They analyze a large number of target compilation languages, including CNF, DNF, PI, IP, DNNF, d-DNNF, FBDD, OBDD, OBDD<, and MODS, according to their succinctness and the polytime operations they support. The paper provides a cross-ranking of these languages, showing their relative succinctness and the queries and transformations they support. It also discusses the importance of these properties in choosing the most suitable target compilation language for a particular application. The authors argue that the analysis of these languages is essential for placing new compilation approaches within the context of existing ones. The paper also highlights the importance of decomposability, determinism, and smoothness in achieving tractability for queries and transformations. The authors conclude that the knowledge compilation map provides a useful framework for evaluating and comparing different target compilation languages.This paper presents a knowledge compilation map that analyzes various target compilation languages based on two key dimensions: the succinctness of the language and the class of queries and transformations it supports in polytime. The authors propose a richer, nested class of target compilation languages based on directed acyclic graphs (DAGs), such as OBDDs, which includes many existing languages. They analyze a large number of target compilation languages, including CNF, DNF, PI, IP, DNNF, d-DNNF, FBDD, OBDD, OBDD<, and MODS, according to their succinctness and the polytime operations they support. The paper provides a cross-ranking of these languages, showing their relative succinctness and the queries and transformations they support. It also discusses the importance of these properties in choosing the most suitable target compilation language for a particular application. The authors argue that the analysis of these languages is essential for placing new compilation approaches within the context of existing ones. The paper also highlights the importance of decomposability, determinism, and smoothness in achieving tractability for queries and transformations. The authors conclude that the knowledge compilation map provides a useful framework for evaluating and comparing different target compilation languages.
Reach us at info@study.space