Complete Inference Rules for the Cancellation Laws

TL;DR

This paper introduces a new set of complete inference rules for handling cancellation laws in automated theorem proving. These rules aim to replace the cancellation axioms themselves, leading to more efficient proofs and fewer redundant consequences compared to traditional methods.

What Problem Does This Paper Address?

Automated theorem provers often struggle with efficiently handling axioms like cancellation laws. While methods like paramodulation can incorporate these axioms, they can lead to a combinatorial explosion of redundant intermediate results. Existing approaches to cancellation laws are often ad hoc and don't fully eliminate the need for the axiom itself. This paper addresses the need for a complete and efficient way to integrate cancellation laws into theorem proving strategies by developing specialized inference rules.

Methods

The authors propose three sets of inference rules for different types of cancellation laws: basic right cancellation, cancellation with identity, and cancellation except for the null element. These rules are designed to be used in conjunction with standard resolution and paramodulation. A key innovation is the introduction of "ground-linear simplification orderings" on terms and literals. These orderings restrict inferences to operate on the "larger" parts of a clause or term, effectively guiding the theorem prover towards more relevant deductions and preventing infinite loops. The paper also discusses how these rules can be further improved by incorporating these orderings, leading to "oriented" versions of resolution and paramodulation.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Replacing Axioms with Rules: The core idea is to replace the abstract cancellation axioms with concrete inference rules. This is a significant shift from simply adding axioms to the theorem prover's knowledge base.
  • Completeness is Key: The proposed inference rules are proven to be complete, meaning they can derive all valid consequences without losing any essential reasoning power.
  • Efficiency Through Guidance: Simplification orderings act as a powerful guidance mechanism, ensuring that inferences are made on "larger" or more significant parts of the problem, thereby pruning the search space and avoiding redundant computations.
  • Generalizability: The framework is shown to be adaptable to different forms of cancellation laws, including those with identity elements and exceptions for null elements, making it applicable to various algebraic theories.

Key Results

The paper presents complete sets of inference rules for three types of cancellation laws. They demonstrate with a simple example how their rules can quickly derive a contradiction in a scenario involving right cancellation. They also mention that these rules can improve the efficiency of the Knuth-Bendix completion procedure, citing a case where a group completion required fewer critical pairs. While quantitative results are not the primary focus, the qualitative improvement in proof efficiency and reduction of redundant consequences is highlighted as a major benefit.

Limitations and Future Work

The authors acknowledge that for space limitations, they are only providing an outline of the rules and the main theorems without proofs. They suggest that the full paper will contain detailed proofs and more examples. They also note that while their approach is complete, other methods like negative paramodulation (introduced by Wos and McCune) can be compatible and further improve efficiency, especially for backward chaining. Future work would likely involve implementing these rules in a theorem prover and conducting extensive empirical evaluations.

Summary updated

BibTeX
@inproceedings{1987complete,
  title = {{Complete Inference Rules for the Cancellation Laws}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure