A Contradiction Separation Dynamic Deduction Algorithm Based on Optimized Proof Search
- 10.2991/ijcis.d.191022.002How to use a DOI?
- Automated theorem proving; Binary resolution; Multi-clause inference rule; S-CS rule; Heuristic strategy
Most of the advanced first-order logic automated theorem proving (ATP) systems adopt binary resolution methods as the core inference mechanism, where only two clauses are involved and a complementary pair of literals are eliminated during each deduction step. Recently, a novel multi-clause inference rule is introduced along with its soundness and completeness, which is called as standard contradiction separation rule (in short, S-CS rule) and allows multiple (two or more) clauses to be involved in each deduction step. This paper introduces and evaluates the application of S-CS rule in first-order logic ATP. Firstly, it analyzes several deduction methods of S-CS rule. It is then focused on how this multi-clause deduction theory can be achieved through forming a specific and effective algorithm, and finally how it can be applied in the top ATP systems in order to improve their performances. Concretely, two novel multi-clause S-CS dynamic deduction algorithms are proposed based on optimized proof search, including related heuristic strategy, then the application method applied in the state of the art ATP system Eprover (the version of Eprover 2.3) is introduced. Eprover with the proposed multi-clause deduction algorithms are evaluated through the FOF division of the CASC-J9 (in 2018) ATP system competition. Experimental results show that Eprover with the proposed multi-clause deduction algorithms outperform the plain Eprover itself to a certain extent.
- © 2019 The Authors. Published by Atlantis Press SARL.
- Open Access
- This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - JOUR AU - Feng Cao AU - Yang Xu AU - Shuwei Chen AU - Jian Zhong AU - Guanfeng Wu PY - 2019 DA - 2019/11/12 TI - A Contradiction Separation Dynamic Deduction Algorithm Based on Optimized Proof Search JO - International Journal of Computational Intelligence Systems SP - 1245 EP - 1254 VL - 12 IS - 2 SN - 1875-6883 UR - https://doi.org/10.2991/ijcis.d.191022.002 DO - 10.2991/ijcis.d.191022.002 ID - Cao2019 ER -