Automatic Case Analysis in Proof by Induction

Adel Bouhoula, Michaël RusinowitchIJCAI 1993

Introduction

Mathematical induction is a fundamental technique in formal verification, essential for proving that hardware or software systems operate correctly across infinite input spaces. However, automating this process remains a significant challenge. Traditional automated theorem provers, such as NQTHM (the Boyer-Moore prover), often require substantial human guidance in the form of intermediate lemmas. Conversely, "inductionless induction" methods based on term rewriting frequently struggle with complex case analysis, often leading to divergent reasoning and infinite loops.

To address these limitations, researchers have developed a new automated procedure implemented in the SPIKE prover. By integrating case analysis directly into term rewriting through a technique called "case rewriting," SPIKE can simulate complex logical reasoning and prove difficult theorems with significantly less human intervention than previous state-of-the-art tools.

Methodology: Case Rewriting and SPIKE

The core innovation of this work is a formal inference system centered on Case Rewriting. This approach treats case analysis not as a logical split that increases complexity, but as a specialized form of term rewriting.

  1. Simulated Case Analysis: Instead of traditional "cut rules" that split a goal $A$ into $C \Rightarrow A$ and $\neg C \Rightarrow A$, the system uses conditional rewrite rules. Preconditions are appended to the goal as a "context," ensuring that every subsequent subgoal is strictly simpler than the original, maintaining a well-founded proof search.
  2. Inductive Positions: SPIKE identifies specific variables in a conjecture that require testing, drastically narrowing the search space and preventing the system from pursuing irrelevant branches.
  3. Non-Hierarchical Architecture: SPIKE is designed for conditional theories and utilizes a flat list of lemmas for mutual simplification. This architecture effectively simulates simultaneous induction, allowing for more flexible reasoning.
  4. Refutational Completeness: For systems employing boolean logic, the method is proven to be refutationally complete; if a conjecture is false, the system is guaranteed to disprove it within a finite timeframe.

Evaluation and Benchmarks

The system was evaluated using classic benchmark problems in automated theorem proving, most notably the Gilbreath Card Trick—a complex mathematical property involving shuffled card sequences. Other benchmarks included conditional equational theories defining functions such as list sorting and parity.

Unlike previous systems that relied on ad-hoc heuristics to select rules, SPIKE’s systematic approach allows it to function without human-defined "milestones." This method also extends beyond simple Horn clauses to more expressive non-Horn clauses, enabling the proof of more complex logical statements.

Key Results

The effectiveness of SPIKE is most clearly demonstrated in its performance on the Gilbreath Card Trick. When compared to other leading provers like NQTHM and RRL, SPIKE required significantly fewer manual definitions and lemmas.

Comparison of user input required for the Gilbreath Card Trick proof across different provers.

As shown in the data, SPIKE successfully proved the trick using only 5 lemmas, compared to 17 for NQTHM and 23 for RRL. Notably, SPIKE required zero manual definitions for implicit functions or induction schemes, demonstrating its ability to handle the structural "heavy lifting" of the proof automatically.

Conclusion and Future Work

While SPIKE is highly effective for "completely defined" functions where ground convergence is maintained, its performance may vary in less constrained theories. Future research directions include integrating case analysis with modern proof-guiding tactics like "rippling-out" and incorporating features from interactive provers to extend SPIKE's capabilities into more abstract mathematical domains. By treating case analysis as a form of rewriting, this work provides a robust framework for increasing the autonomy of inductive theorem provers.

Summary updated

BibTeX
@inproceedings{bouhoula1993automatic,
  author = {Adel Bouhoula and Michaël Rusinowitch},
  title = {{Automatic Case Analysis in Proof by Induction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
}
Figure