A relaxation approach to splitting in an automatic theorem prover

摘要

The splitting of a problem into subproblems often involves the same variable appearing in more than one of the subproblems. This makes these subproblems dependent upon one another since a solution to one may not qualify as a solution to another. A two stage method of splitting is described which first obtains solutions by relaxing the dependency requirement and then attempts to reconcile solutions to different subproblems. The method has been realized as part of an automatic theorem proper programmed in lisp which takes advantage of the procedural power that lisp provides. The program has had success with cryptarithmetic problems, problems from the blocks world, and has been used as a subroutine in a plane geometry theorem prover.