Preserving Consistency Across Abstraction Mappings

TL;DR

This paper introduces "predicate mappings," a way to simplify complex logical theories by renaming predicate symbols. The key innovation is a "restricted predicate mapping" that guarantees consistency in the abstract theory, even if the original theory is complex, by carefully selecting which clauses to carry over. This allows for more efficient problem-solving by working with a simpler, yet consistent, abstract representation.

What Problem Does This Paper Address?

Many real-world problems, especially in areas like automated reasoning and planning, can be represented using complex first-order logic theories. Solving these problems directly can be computationally intractable due to the sheer size and complexity of the theories. A common strategy to combat this is "abstraction," where the problem is mapped to a simpler, abstract representation. The abstract solution is then used to guide the search in the original, more complex problem space.

However, a significant challenge with existing abstraction methods, particularly those proposed by Plaisted, is that they can inadvertently introduce inconsistencies into the abstract theory, even if the original theory was perfectly consistent. This "false proof" problem undermines the utility of abstraction. This paper addresses the need for abstraction methods that preserve consistency, making them more reliable for practical applications.

Methods

The paper defines "predicate mappings" as functions that rename predicate symbols from an original theory (L1) to an abstract theory (L2). Crucially, these mappings are not necessarily one-to-one; multiple original predicates can map to a single abstract predicate. This is the core mechanism for simplification.

To address the consistency issue, the authors introduce "restricted predicate mappings." This is a syntactic restriction on which clauses from the original theory are carried over to the abstract theory. The restriction is based on ensuring that only clauses that don't "distinguish" the predicates being conflated are included. Specifically, for a clause C in the abstract theory, it must be derivable from the original theory, and if C is a positive clause, it must be derivable from the original theory. If C contains negated literals, it must be derivable from the original theory, and for each literal in C, there must be a corresponding clause in the original theory that maps to it and is derivable. This careful selection process is designed to prevent the introduction of contradictions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Abstraction as a Search Simplification Tool: The paper frames abstraction as a powerful technique for reducing the search space in computationally hard problems, making them more tractable.
  • The "False Proof" Problem: A critical insight is the inherent risk of abstraction methods introducing inconsistencies, which can lead to incorrect conclusions. This paper directly tackles this by ensuring consistency.
  • Semantics of Restricted Mappings: The paper proposes an intuitive semantics for restricted predicate mappings: the interpretation of an abstract predicate is the union of the interpretations of the original predicates that map to it. This provides a clear conceptual understanding of what the abstraction represents.
  • Downward-Solution Property: While restricted mappings might lose the "upward-solution property" (where every abstract solution has a corresponding original solution), they gain a "downward-solution property." This means every derivable clause in the abstract theory has a specialized version derivable in the original theory, offering a form of guarantee.

Key Results

The central result is a theorem proving that given a consistent original theory and a restricted predicate mapping, the resulting abstract theory is also consistent. This is demonstrated constructively by showing how to build a model for the abstract theory from a model of the original theory. The paper provides a formal proof for this theorem, covering both positive and negated literal cases in clauses.

Limitations and Future Work

  • Undecidability of Derivability: The definition of restricted predicate mappings relies on checking derivability of clauses, which is generally undecidable. The authors acknowledge this and suggest that practical implementations would involve bounding the search for derivability, accepting that this might lead to a weaker abstract theory (fewer theorems) but still preserving consistency.
  • Upward-Solution Property Loss: The restricted mappings do not guarantee the upward-solution property, meaning an abstract solution might not directly translate to an original solution. This is a trade-off for guaranteed consistency.
  • Performance Choices: The paper notes that determining the appropriate amount of resources to expend in constructing abstract theories is an important issue for future work, particularly in the context of performance.

Summary updated

BibTeX
@inproceedings{1987preserving,
  title = {{Preserving Consistency Across Abstraction Mappings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure