Compiling Circumscriptive Theories into Logic Programs: Preliminary Report

AAAI 1988

TL;DR

This paper explores how to translate certain types of circumscriptive theories, a powerful formalism for nonmonotonic reasoning, into logic programs. This compilation allows us to leverage existing logic programming tools to automatically reason about these theories, particularly for complex knowledge representation tasks like inheritance systems.

What Problem Does This Paper Address?

Commonsense reasoning often involves dealing with incomplete information and exceptions. Circumscription, introduced by John McCarthy, provides a formal way to capture this by minimizing certain predicates, effectively treating unstated exceptions as abnormal. However, determining whether a statement follows from a circumscriptive theory can be computationally challenging. Logic programming, on the other hand, offers a well-established framework for automated reasoning. This paper bridges this gap by investigating how to compile circumscriptive theories into logic programs, enabling the use of logic programming interpreters to answer queries about these nonmonotonic theories.

Methods

The core idea is to transform a given circumscriptive theory $(A, C)$ (axioms $A$ and circumscription policy $C$) and a goal formula $F$ into a logic program $\Pi$ and a query $W$. The rules of $\Pi$ are derived from the axioms $A$, potentially modified to reflect the circumscription policy $C$. The query $W$ is often a syntactic transformation of $F$.

The compilation process involves several steps:

  • Dropping Uniqueness of Names Axioms: For simple cases, the logic program $\Pi$ is formed by simply removing the uniqueness of names axioms from the axiom set $A$.
  • Handling Clauses: Clauses that are not directly rules (e.g., negative clauses) need to be transformed. This can involve replacing negated predicates with new predicate symbols (e.g., flies becomes flies) and introducing new axioms to capture the relationship between the original and new predicates.
  • Resolution: To handle more complex interactions between axioms, especially when dealing with exceptions and priorities, the authors employ resolution. This process derives new clauses by combining existing ones, which are then converted into rules.
  • Stratification: The resulting logic program must be stratified, meaning its predicates can be partitioned into layers with specific ordering constraints. This stratification is crucial for defining the semantics of the program, especially when negation is involved. The authors propose a stratification based on the priorities defined in the circumscription policy.

The paper also introduces a formal theorem (Theorem 1) that establishes the correctness of this compilation process for a specific class of circumscriptive theories and logic programs.

Datasets

Not discussed in the paper. The paper focuses on formal methods and theoretical compilation rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Logic Programming as a Reasoning Engine for Circumscription: The paper demonstrates that logic programming, with its well-defined semantics and efficient interpreters, can serve as a powerful tool for automating reasoning with circumscriptive theories.
  • Compilation as a Bridge: The compilation process is the key to connecting these two formalisms. It's not a direct mapping but involves transformations like predicate renaming and resolution to capture the nuances of circumscription.
  • Stratification Reflects Priorities: The stratification of the compiled logic program directly mirrors the priority assignments in the circumscription policy, allowing the logic programming semantics to capture the intended nonmonotonic reasoning.
  • Handling Exceptions: The methods are particularly effective for formalizing systems with exceptions, such as tree-structured inheritance systems, where minimizing abnormality predicates is a natural fit for logic programming's minimization principles.

Key Results

The paper presents a theoretical framework and a set of examples demonstrating the compilation of circumscriptive theories into logic programs. Theorem 1 provides a formal guarantee for the correctness of this compilation for a significant class of theories. The examples illustrate how this approach can be used to determine the provability of ground literals in circumscriptive theories, including those with prioritized minimization and exceptions. The paper shows that the number of rules in the compiled program is polynomial in the number of clauses in the original axiom set.

Limitations and Future Work

  • Assumptions on Axiom Form: The method has strong assumptions about the form of the circumscriptive theory and the goal formula. Specifically, axioms must be clauses, and predicates in the "varied" list (Z) can appear in at most one literal in any clause.
  • Fixed Predicates: The current method is not directly applicable to circumscriptions where some predicates are explicitly "fixed" (not minimized).
  • Multiple Inheritance Systems: While the paper touches upon multiple inheritance systems, it notes that some complex cases, particularly those involving overlapping classes and conflicting priorities, can lead to clauses that cannot be stratified by the proposed method.
  • Optimizations: The paper mentions that some "optimizations" (like dropping redundant literals) are ignored for clarity but could be incorporated.
  • Future Work: The authors suggest exploring extensions to handle fixed predicates and more complex scenarios in multiple inheritance systems. The full paper is promised to contain proofs and further extensions.

Summary updated

BibTeX
@inproceedings{1988compiling,
  title = {{Compiling Circumscriptive Theories into Logic Programs: Preliminary Report}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure