Parallel Knowledge Compilation Algorithms for EPCCL Theory

NIU Dang-dang; LIU Lei; L

doi:10.3969/j.issn.0372-2112.2018.03.004

您当前的位置：

首页 >

文章列表页 >

Parallel Knowledge Compilation Algorithms for EPCCL Theory

更新时间：2025-07-16

- Parallel Knowledge Compilation Algorithms for EPCCL Theory
- Acta Electronica Sinica Vol. 46, Issue 3, Pages: 537-543(2018)
- 作者机构：
  
  1. 吉林大学计算机科学与技术学院,吉林,长春,130012
  2. 符号计算与知识工程教育部重点实验室(吉林大学),吉林,长春,130012
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China (No.61300049, No.61502197, No.61503044);Research Fund for the Doctoral Program of Higher Education of Ministry of Education of China (No.20120061120059);Scientific Research Fund for Youth of Jilin Province (No.20140520069JH, No.20150520058JH);Natural Science Foundation Project of Jilin Province (No.20150101054JC)
- DOI：10.3969/j.issn.0372-2112.2018.03.004
  CLC： TP301TP181
- Published Online：25 March 2018，
  
  Published：2018
- 稿件说明：
移动端阅览
NIU Dang-dang, LIU Lei, L. Parallel Knowledge Compilation Algorithms for EPCCL Theory[J]. Acta Electronica Sinica, 2018, 46(3): 537-543.
DOI：

NIU Dang-dang, LIU Lei, L. Parallel Knowledge Compilation Algorithms for EPCCL Theory[J]. Acta Electronica Sinica, 2018, 46(3): 537-543. DOI： 10.3969/j.issn.0372-2112.2018.03.004.

摘要

基于超扩展规则，证明了EPCCL（Each Pair Contains Complementary Literal）理论的合并过程是可并行执行的，并设计了针对多个EPCCL理论的并行合并算法PUAE（Parallel computing Union of Any number of EPCCL）.通过对EPCCL理论原始子句集的利用，提出了另一种高效的EPCCL理论并行合并算法imp-PUAE（improvement of PUAE）.UKCHER（computing Union sets of maximum terms for Knowledge Compilation based on Hyper Extension Rule）是一种可并行的EPCCL理论编译算法，分别利用PUAE和imp-PUAE设计了两个并行知识编译算法P-UKCHER（UKCHER with PUAE）和impP-UKCHER（UKCHER with imp-PUAE）.实验结果表明：P-UKCHER算法虽然没有提升UKCHER算法的效率，但能够提升UKCHER算法编译结果的质量，最好情况下可提升4倍；而impP-UKCHER算法能够提高UKCHER算法的效率，同时也能够提升编译结果的质量，同样最好情况下可提升4倍.

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.

关键词

Keywords

references

Views

203

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Knowledge Compilation Algorithm of Computing Difference Based on MACR Heuristics and CAL Heuristics

Knowledge Compilation Algorithm of Computing Difference Based on MOVR Heuristics

An Extension Rule Algorithm Based on Local Search with IAPS Strategies

Related Author

NIU Dang-dang

LV Shuai

WANG Jin-yan

LIU Bin

Shuai

WANG Jin-yan

HU Chun

NIU Dang-dang

Related Institution

农业农村部农业物联网重点实验室(西北农林科技大学) 陕西杨凌

陕西省农业信息感知与智能服务重点实验室(西北农林科技大学) 陕西杨凌

西北农林科技大学信息工程学院陕西杨凌

广西师范大学计算机科学与信息工程学院

符号计算与知识工程教育部重点实验室(吉林大学)

⁰