Knowledge compilation is a family of approaches for addressing the intractability of
a number of
artificial intelligence problems.
A propositional model is compiled in an off-line phase in order to support some queries in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. Many ways of compiling a propositional models exist.
[Adnan Darwiche, Pierre Marquis,]
A Knowledge Compilation Map
, Journal of Artificial Intelligence Research 17 (2002) 229-264
Different compiled representations have different properties.
The three main properties are:
* The compactness of the representation
* The queries that are supported in polynomial time
* The transformations of the representations that can be performed in polynomial time
Classes of representations
Some examples of
diagram classes include
OBDDs,
FBDDs, and non-deterministic OBDDs, as well as
MDD.
Some examples of
formula
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwee ...
classes include
DNF and
CNF.
Examples of circuit classes include
NNF, DNNF, d-DNNF, and
SDD.
References
Artificial intelligence
{{Compu-AI-stub