Application of Automatic Transformations to Program Verification

Abstract

A technique for incorporating automatic transformations into processes such as the application of inference rules, subsumptlon, and demodulation provides a mechanism for improving search strategies for theorem proving problems arising from the field of program verification. The incorporation of automatic transformations into the inference process can later the search space for a given problem and is particularly useful for problems having broad rather than deep proofs. The technique can also be used to permit the generation of inferences that might otherwise be blocked and to build some commutatlvlty or associativity into the unification process. Appropriate choice of transformations and new literal clashing and unification algorithms for applying them showed significant improvement on several real problems according to several distinct criteria.