Proof Lengths for Equational Completion

We first show that ground term-rewriting systems can be completed in a polynomial number of rewriting steps, if the appropriate data structure for terms is used. We then apply this result to study the lengths of critical pair proofs in non-ground systems, and obtain bounds on the lengths of critical pair proofs in the non-ground case. We show how these bounds depend on the types of inference steps that are allowed in the proofs.

Authors

• David A. Plaisted
• Andrea Sattler-Klein

Keywords

No keywords are indexed for this paper.