×

Efficiency and completeness properties of the counting method. (English) Zbl 0676.68054

Summary: The Counting method rewrites a logic (conceived for a backward, Prolog- like, evaluation) into another set of clauses that can be efficiently executed using a forward strategy. We assume here a forward evaluation strategy based on the saturation (of a set of clauses) operator. Under this hypothesis, the rewriting method is compared with the original logic environment by means of a stack machine, which is used as a reference environment for our comparison. By proving different correspondences between the stack history tree nodes and the atoms produced during the saturation we characterize the Counting approach as for efficiency w.r.t. shortcuts or cyclic relations and as for completeness and soundness.

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
03B35 Mechanization of proofs and logical operations