A multi-clause dynamic deduction algorithm based on standard contradiction separation rule

Feng Cao, Yang Xu, J. Liu, Shuwei Chen, Jianbing Yi

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
3 Downloads (Pure)

Abstract

In the past decades, automated theorem proving (ATP) for first-order logic has made good progress, in which binary resolution inference rule plays a crucial role. However, as shown in the latest benchmark library of the ATP system, there are still many practical problems that have not been resolved or cannot be effectively resolved. Recently, in order to over-come the limitations of ATP based on binary resolution inference rules, a novel multi-clause dynamic standard contradiction separation (S-CS) inference rule and its automated deduction theory have been proposed. Based on this theory, this paper first clarifies the generality of this S-CS rule by comparing it with some well-known variants of the binary resolution rule, and then focuses on how to design a specific and effective algorithm along with search strategies to realize the S-CS based deductive theory with its implementation. Specifically, the present work proposes a novel S-CS dynamic deduction algorithm (in short SDDA) based on different strategies and summarizes its implementation procedures. In addition, we focus on evaluating whether SDDA, as a novel perspective multi-clause dynamic automatic deduction algorithm, can be applied on top of the current leading ATP system architectures to further improve their performances. Therefore, SDDA is applied to the current leading first-order ATP systems, i.e., Vampire and E, respectively forming two integrated APT systems, denoted as SDDA_V and SDDA_E. Then the capabilities of SDDA_V and SDDA_E are evaluated on the latest benchmark database TPTP, such as the CASC-J9 problems (FOF division) as well as the hard problems with a rating of 1 in the TPTP benchmark database. The experimental results show the effectiveness of SDDA:SDDA_V outperforms Vampire itself, and SDDA_E, outperforms E itself, and the two improved ATP systems have solved a number of hard problems with the rating of 1 in TPTP, that is, some problems in the latest benchmark database TPTP which have not yet been solved by other current first-order ATP systems.
Original languageEnglish
Pages (from-to)281-299
Number of pages19
JournalInformation Sciences
Volume566
Early online date17 Mar 2021
DOIs
Publication statusPublished - 31 Aug 2021

Bibliographical note

Funding Information:
This paper is supported by the Natural Science Foundation of China (Grant No. 61673320 ); The Natural Science Foundation of Jiangxi Province (Grant No. 20181BAB202004 ); The General Research Project of Jiangxi Education Department (Grant No. GJJ200818); The Humanities and Social Sciences Research Project of the Ministry of Education of P. R. China (Grant No. 20XJCZ H016 ).

Publisher Copyright:
© 2021 Elsevier Inc.

Keywords

  • ATP systems
  • Automated theorem proving
  • Binary resolution
  • First-order logic
  • S-CS dynamic deduction
  • Standard contradiction separation

Fingerprint

Dive into the research topics of 'A multi-clause dynamic deduction algorithm based on standard contradiction separation rule'. Together they form a unique fingerprint.

Cite this