Abstract
Automated theorem proving often struggles with the exponential growth of search spaces. Abstraction—mapping a complex "ground" problem to a simplified "abstract" space—is a common mitigation strategy, yet it has lacked a unified formal theory. This paper establishes a comprehensive framework for abstraction, defining it as a mapping between formal systems. We classify abstractions based on theorem preservation and address the critical "false proof problem," where abstract inconsistencies mislead the reasoner. By introducing a partial order of abstractions and hierarchical refinement, we provide a systematic method for leveraging abstract proofs to guide ground-level search effectively.
Introduction
In the field of automated reasoning, the search for a proof can be computationally prohibitive due to the vastness of the search space. Abstraction offers a way to manage this complexity by simplifying the problem, finding a solution in the abstract domain, and using it as a template for the original ground problem. However, the application of abstraction has historically been fragmented across sub-fields like hierarchical planning and resolution theorem proving. Furthermore, the "false proof problem"—where an abstraction becomes inconsistent and allows for the derivation of any formula—remains a significant hurdle. This paper provides the first unified formal theory to address these challenges.
A Formal Theory of Abstraction
The authors define a formal system $\Sigma$ as a triple $\langle L, \Lambda, \Delta \rangle$, consisting of a language $L$, a set of axioms $\Lambda$, and a deductive machinery $\Delta$. An abstraction is then defined as a mapping $f: \Sigma_1 \to \Sigma_2$ between two such systems.
Classification of Abstractions
Abstractions are categorized by how they preserve the properties of the ground space:
- Theorem Increasing (TI): Every theorem in the ground space has a corresponding theorem in the abstract space. This is the most common form, used to ensure that if a proof exists in the ground space, a "shadow" of it exists in the abstract space.
- Theorem Decreasing (TD): Only a subset of ground theorems are preserved in the abstract space.
- Theorem Constant (TC): The set of theorems remains invariant under the mapping.
- Negation/Inconsistency Preserving (NT): These mappings focus on the preservation of non-theorems or inconsistencies, which is vital for resolution-based provers to avoid "false proofs."
The paper also introduces a partial order of abstractions ($\sqsubseteq$), which allows for the ranking of abstractions by their "strength" or level of detail.
Case Studies and Unification
To validate the framework, the authors apply it to three major existing techniques:
- ABSTRIPS: A hierarchical planning system where abstractions are formed by dropping preconditions.
- Resolution Abstractions: Mappings used in resolution theorem proving to simplify clauses.
- Theory of Granularity: A method for simplifying theories by clustering indistinguishable objects into single entities.
A key insight is the mathematical unification of these techniques; for instance, the authors demonstrate that Hobbs’ theory of granularity is a special case of Plaisted’s resolution abstractions.
Results: Solving the False Proof Problem
The "false proof problem" occurs when an abstraction is too coarse, leading to an inconsistent abstract theory where any statement can be "proven." The authors prove that this problem is theoretically inevitable for certain classes of abstractions.
To mitigate this, they propose Hierarchical Refinement. By using a chain of abstractions $f_1 \sqsubseteq f_2 \sqsubseteq ... \sqsubseteq f_n$, a reasoner can start with the simplest, most abstract space. If a proof is found, it is checked against increasingly "stronger" (more detailed) abstractions. This allows the system to filter out false proofs early and pivot to alternative search paths before committing to expensive ground-level computations.
Conclusion
This work establishes a rigorous mathematical foundation for abstraction in automated reasoning. By classifying mappings and introducing a hierarchical refinement procedure, the authors provide a systematic way to reduce search complexity while avoiding the pitfalls of abstract inconsistency. Future work will focus on the computational costs of maintaining these hierarchies and developing heuristics for selecting optimal abstractions for novel problems.
Summary updated