电子学报2018，Vol.46Issue(3)：537-543,7.DOI:10.3969/j.issn.0372-2112.2018.03.004
EPCCL理论的并行知识编译算法
Parallel Knowledge Compilation Algorithms for EPCCL Theory
摘要
Abstract
Based on HER (hyper extension rule), we prove that the parallelization of merging multiple EPCCL (each pair contains complementary literal) is feasible, and the corresponding algorithm PUAE (parallel computing union of any number of EPCCL) is proposed. Through using the origin CNF formulae of EPCCL theories, another efficient merging algorithm imp-PUAE (improvement of PUAE) is proposed. UKCHER (computing union sets of maximum terms for knowledge compilation based on hyper extension rule) is a knowledge compilation algorithm for EPCCL, which can be parallelized. Based on the above methods, we proposed two parallel knowledge compilation algorithms i. e., P-UKCHER (UKCHER with PUAE) and impP-UKCHER (UKCHER with imp-PUAE), which use the PUAE algorithm and imp-PUAE algorithm, respectively. Experimentally, although P-UKCHER does not improve the efficiency of UKCHER, the compilation quality is improved. In the best case, the compilation quality can be improved by 4 times with P-UKCHER. The impP-UKCHER can improve the efficiency and compilation quality of UKCHER at the same time, and the compilation quality can also be improved by 4 times in the best case.关键词
知识编译/扩展规则/超扩展规则/EPCCL理论/并行编译Key words
knowledge compilation/extension rule/hyper extension rule/EPCCL theory/parallel compilation分类
信息技术与安全科学引用本文复制引用
牛当当,刘磊,吕帅..EPCCL理论的并行知识编译算法[J].电子学报,2018,46(3):537-543,7.基金项目
国家自然科学基金(No.61300049,No.61502197,No.61503044) （No.61300049,No.61502197,No.61503044）
教育部高等学校博士学科点专项科研基金(No.20120061120059) （No.20120061120059）
吉林省青年科研基金项目(No.20140520069JH,No.20150520058JH) （No.20140520069JH,No.20150520058JH）
吉林省自然科学基金项目(No.20150101054JC) （No.20150101054JC）
