[Back]

G. Reger, M. Suda, A. Voronkov:
"New Techniques in Clausal Form Generation";
Talk: GCAI 2016 / 2nd Global Conference on Artificial Intelligence, Berlin, Germany; 2016-09-29 - 2016-10-02; in: "GCAI 2016. 2nd Global Conference on Artificial Intelligence", EasyChair, EPiC Series in Computing / 41 / Berlin (2016), 11 - 23.

In automated reasoning it is common that first-order formulas need to be translated into clausal normal form for proof search. The structure of this normal form can have a large impact on the performance of first-order theorem provers, influencing whether a proof can be found and how quickly. It is common folklore that translations should ideally minimise both the size of the generated clause set and extensions to the signature. This paper introduces a new top-down approach to clausal form generation for first-order formulas that aims to achieve this goal in a new way. The main advantage of this approach over existing bottom-up techniques is that more contextual information is available at points where decisions such as subformula-naming and skolemisation occur. Experimental results show that our implementation of the translation in Vampire can lead to clausal forms which are smaller and better suited to proof search.

First-Order Logic, Automated Reasoning, Theorem Proving, Clausal Normal Form, Clausification

http://publik.tuwien.ac.at/files/publik_255029.pdf