A New Structural Induction Scheme for Proving Properties of Mutually Recursive Concepts

Peiya Liu, Ruey-Juin ChangAAAI 1987

Abstract

Automated theorem proving systems have long relied on structural induction to verify properties of recursive programs. However, traditional "weak" induction schemes often fail when applied to mutually recursive functions—where multiple functions call each other in a cycle. This paper presents a generalized structural induction principle that natively handles mutual recursion by generating induction hypotheses that mirror the recursive structure of the definitions. By formalizing "strong" induction schemes and hypothesis terms, the authors provide a framework that allows mechanical provers to automate proofs for complex, interdependent data structures and functions without requiring manual "flattening" of the recursion.

Introduction

In the domain of formal methods and automated reasoning, structural induction is the primary tool for proving properties of programs. In the 1980s, systems like the Boyer-Moore prover demonstrated significant success in verifying self-recursive functions—functions that operate on a smaller component of their own input (e.g., processing a list by recurring on its tail).

Despite these successes, a significant gap remained: mutually recursive concepts. When Function A calls Function B, and Function B calls Function A, standard induction schemes typically fail to generate the necessary induction hypotheses to complete a proof. Historically, researchers bypassed this by manually transforming mutual recursion into a single, self-recursive function using "switch" arguments. This process, known as flattening, is unnatural, error-prone, and difficult to automate. This paper introduces a new scheme designed to bridge this gap by treating mutual recursion as a first-class citizen in the inductive process.

The Generalized Structural Induction Principle

The core innovation of this work is the transition from "weak" induction to a "strong" induction framework. The authors propose a Generalized Structural Induction Principle based on three primary components:

1. Strong Induction Schemes and Hypothesis Terms

Unlike simple induction, which provides a single hypothesis for a single recursive call, the proposed system generates "Hypothesis Terms." These terms are themselves recursive concepts that "unroll" the mutual calls. For instance, if a conjecture involves a function $f_1$ that calls $f_2$, the induction hypothesis for $f_1$ is constructed to incorporate the logical structure of $f_2$. This ensures that the induction scheme maintains structural similarity with the function definitions, which the authors argue is the key to successful mechanical induction.

2. The Definition Principle

To ensure logical consistency, the paper formalizes how a set of $n$ axioms can constitute a valid recursive definition. Central to this is the requirement of a well-founded relation—a measure of "size" that must decrease with every recursive call. This ensures that the recursion eventually terminates, preventing the introduction of logical paradoxes into the prover's environment.

3. Heuristic Mixing

Rather than replacing existing methods, the authors describe a method for "mixing" these new strong schemes with traditional weak ones. This allows a theorem prover to heuristically combine different induction strategies to synthesize the most effective approach for a specific conjecture. This hybrid approach preserves the efficiency of simple induction for basic tasks while providing the power needed for complex mutual recursion.

Evaluation and Benchmarks

As a theoretical contribution to formal logic, the paper evaluates the proposed scheme using classic functional programming benchmarks rather than empirical datasets. Key examples include:

  • EVAL and EVAL.LIST: A classic instance of mutual recursion where an expression evaluator calls a list evaluator for arguments, which in turn calls the expression evaluator.
  • QuickSort (QSORT): Used to demonstrate the scheme's ability to handle complex partitioning logic and non-trivial termination arguments.
  • FOO and FOOLIST: Abstract functions used to formally trace the algorithm for generating hypothesis terms from function bodies.

Key Insights

The paper's primary insight is that mechanical induction is most effective when the induction scheme's structure mirrors the function's recursive structure. Weak induction fails for mutual recursion precisely because it breaks this structural similarity. By describing hypotheses implicitly through recursive terms rather than explicit lists of sub-cases, the authors provide a more powerful and flexible automation strategy.

Furthermore, the work emphasizes integration. By providing a generalized principle, the authors allow provers to choose the "weak" path for simple recursion and the "strong" path for mutual recursion, ensuring the system remains performant across a wide range of problems.

Conclusion and Future Work

The formalization of hypothesis terms and the accompanying soundness proofs (detailed in Liu’s 1986 thesis) represent a significant step toward fully automated verification of complex software. By removing the need for human-provided "hints" or manual flattening of recursive definitions, this scheme moves automated provers closer to handling real-world, nested data structures.

However, challenges remain. The complexity of the heuristics required to "mix" induction schemes effectively is significant, and the system still relies on the provision of a "measure function" to prove termination—a problem that remains difficult in the general case. Future research will focus on integrating these schemes into logic program interpreters and exploring their performance on even more deeply nested recursive structures.

Summary updated

BibTeX
@inproceedings{liu1987new,
  author = {Peiya Liu and Ruey-Juin Chang},
  title = {{A New Structural Induction Scheme for Proving Properties of Mutually Recursive Concepts}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}

Loading related content...

Figure