2.1.5 知识编译
命题推理问题通常被认为是不易处理的。例如，命题知识库的子 句蕴含查询为 co-NP 完全问题，通常被认为不存在多项式时间的求解 算法。知识编译是解决这种不易处理性问题的重要方法[14] [15] [52] ，目前已被应用到模型检测[53] 、诊断[54] 、产品配置[55] 、自动规划[56] 、数据库[57] 和数据挖掘[58] 等多个领域。命题推理问题可从概念上分 为知识库和查询两部分，其中知识库的更新频率较低，人们通常需要 对同一知识库做多次查询。知识编译的主要思想是将查询应答过程分 成两个阶段：离线的编译阶段(off-line compilation phase)和在线的查询 应答阶段(online query-answering phase)。在离线时将命题公式编译为 易处理的目标语言(target language)，从而能更有效地回答在线阶段的 查询。离线阶段的时间代价能在多次（甚至指数次）的在线查询中通 过类似于分期付款的方式补偿回来。
目标语言是任意知识编译方法的重要方面，其最基本的要求是需满足多项式时间的子句蕴含查询。目前在实际中应用较为广泛的目标语言主要可分为如下三大类。第一类为 CNF 和 DNF 的子集，主要包括 Horn 理论[14] [59] 、 本原蕴含式/ 本原蕴含范式（ prime implicates/implicants normal form，PI/IP）[60] [61] [62] [63] 、EPCCL（each pair containing complementary literals）理论[65] 、MODS（models）[52]等。第二类为有序二元决策图（ordered binary decision diagram，OBDD）
[66] 及其推广。第三类为可分解否定范式（ decomposable negation
normal form，DNNF）[22] 及其子集。
由于到目前为止研究人员针对不同的推理问题提出了多种知识编译语言，从而增加了在实际应用中选择合适编译语言的困难性。鉴于此，文献[52] 主张按照如下三个标准对知识编译语言进行评估：简洁性（succinctness），多项式时间内支持的查询的种类以及多项式时间内支持的转化的种类。
文献[52] 按照上述三种标准对多种知识编译语言进行了评估，并将评估结果形成了一个知识编译图谱（knowledge compilation map）。之后，研究人员多次对知识编译图谱进行了扩展。
除了知识编译图谱中涉及到的三个重要评价标准外，知识编译语 言是否具有规范性（canonicity，即对于任意知识库，对应编译结果是 唯一的）也是实际应用中选择知识编译语言需要考虑的一个重要因素，其能极大方便搜索最优编译结果。例如，OBDD 在实际中广泛应用的 一个重要因素即为ROBDD 具有规范性，且能在线性时间内通过等价 的 OBDD 得到 ROBDD[67] 。
国内吉林大学最早开展了知识编译的研究，提出了 EPCCL、 OBDD[]、CCDD 等知识编译语言，并设计了多个编译器。