微信服务号

微信订阅号

2025-4-24- 10
Home > Archive>Volume 32, Issue 9, 2021 >2744-2754. DOI:10.13328/j.cnki.jos.005974
PDF HTML XML Export Cite reminder
Local Search-based Parallel Extension Rule Reasoning Method
Author:
Affiliation:

Clc Number:

TP181

Fund Project:

National Key Research and Development Program of China (2017YFB1003103); National Natural Science Foundation of China (61300049, 61763003); Natural Science Research Foundation of Jilin Province of China (20180101053JC, 20190201193JC, 20190103005JH); Graduate Innovation Fund of Jilin University of China (101832018C025)

  • Article
    • | |
  • Metrics
    • |
  • Reference
    • |
  • Related
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    Extension rule reasoning method has been widely used in solving the classical satisfiability problem. Several reasoning methods based on extension rule have been proposed, which have been recognized around the world. These methods include the complete algorithms like NER, IMOMH_IER, PPSER, and local search-based incomplete algorithm like ERACC. All of them have sound performance. ERACC algorithm is the most efficient and powerful algorithm in the current extension rule solver. However, the serial algorithm ERACC still needs improvement on heuristics and preprocessing. Therefore, a parallel framework is designed and it is called PERACC algorithm. Based on the configuration checking of local search method, the algorithm decomposes the original maximum term space into several maximum term subspaces, from three stages of assigning initial values to variables, simplifying solution space, and heuristic, simplifying the original clause set, then processing each subspace in parallel. Experiments show that, compared with the original algorithm, the proposed algorithm not only can improve the efficiency of solution, but also can solve larger benchmark, which makes the extension rule method break through the limitation of formula size again.

    Reference
    Related
    Cited by
Get Citation

李壮,刘磊,张桐搏,周文博,吕帅.基于局部搜索的并行扩展规则推理方法.软件学报,2021,32(9):2744-2754

Copy
Share
Article Metrics
  • Abstract:2737
  • PDF: 4187
  • HTML: 1772
  • Cited by: 0
History
  • Received:February 28,2019
  • Revised:August 25,2019
  • Online: December 06,2019
  • Published: September 06,2021
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063