A knowledge compilation map
A knowledge compilation map
复制标题
DOI：
10.1613/jair.989
复制
发表时间：
2002-01-01
影响因子：
5
通讯作者：
Marquis, P
中科院分区：
文献类型：
--
作者：
Darwiche, A;Marquis, P
我们提出了一种知识编译的观点，要求从两个关键维度来分析不同的编译方法：目标编译语言的简洁性，以及该语言在多时间内支持的查询和转换的类别。在此基础上，给出了一种知识编译地图，该地图根据目标编译语言的简洁性以及它们的多次转换和查询来分析现有的大量目标编译语言。我们认为，这种分析对于将新的汇编方法置于现有汇编方法的背景下是必要的。我们还超越了基于CNF和DNF的经典扁平目标编译语言，并考虑了一个基于有向无环图(如OBDDS)的更丰富的嵌套类，我们展示了它包括了相对较多的目标编译语言。
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.