Related resources
Search for item elsewhere
University researcher(s)
Academic department(s)
Practical Aspects of Automated First-Order Reasoning
[Thesis]. Manchester, UK: The University of Manchester; 2012.
Access to files
-
FULL-TEXT.PDF (pdf)
Abstract
Our work focuses on bringing the first-order reasoning closer to practicalapplications, particularly in software and hardware verification.The aim is to develop techniques that make first-order reasoners more scalablefor large problems and suitable for the applications.In pursuit of this goal the work focuses in three main directions. First, wedevelop an algorithm for an efficient pre-selection of axioms. This algorithmis already being widely used by the community and enables off-the-shelf theoremprovers to work with problems having millions of axioms that would otherwisebe overwhelming for them.Secondly, we focus on the saturation algorithm itself, and develop anew calculus for separate handling of propositional predicates. We also do anextensive research on various ways of clause splitting within the saturationalgorithm.The third main block of our work is focused on the use of saturation basedfirst-order theorem provers for software verification, particularly forgenerating invariants and computing interpolants.We base our work on theoretical results of Kovacs and Voronkov published in2009 on the CADE and FASE conferences. We develop a practical implementationwhich embraces all the extensions of the basic resolution and superposition calculus that are contained in the theorem prover Vampire. We have also developed a unique proof transforming algorithm which optimizes the computed interpolantswith respect to a user specified cost function.