Controlling the Consumption of Storage with Sliding Priority Search in a Hyper-Linking Based Theorem Prover

Abstract

The hyper-linking strategy proposed in [17] eliminates duplication of instances of clauses during the process of inference. However, hyper/instances were generated exhaustively by breadth/first search which may cause memory-paging troubles for hard problems since all hyper-instances have to be stored and processed. We present a sliding priority search to provide control on the number of hyper-instances saved and the amount of memory consumed by discarding those instances whose priority value exceeds a priority bound. The bound is set automatically rather than by the user. A technique similar to iterative deepening is also applied to preserve completeness of the hyper-linking strategy. The sliding priority method enabled us to get a number of proofs that could not be obtained with breadth-first search.