Knowledge compilation explained

Knowledge compilation is a family of approaches for addressing the intractability ofa number of artificial intelligence problems.

A propositional model is compiled in an off-line phase in order to support some queries in polynomial time. Many ways of compiling a propositional model exist.[1]

Different compiled representations have different properties.The three main properties are:

Classes of representations

Some examples of diagram classes include OBDDs, FBDDs, and non-deterministic OBDDs, as well as MDD.

Some examples of formula classes include DNF and CNF.

Examples of circuit classes include NNF, DNNF, d-DNNF, and SDD.

Knowledge compilers

References

  1. Adnan Darwiche, Pierre Marquis, "A Knowledge Compilation Map", Journal of Artificial Intelligence Research 17 (2002) 229-264