Abstract
This paper establishes a formal bridge between logic programming and automated reasoning by utilizing an Assumption-Based Truth Maintenance System (ATMS) to compute stable models. By transforming negation into a set of explicit assumptions, the proposed algorithm provides a concrete methodology for finding consistent interpretations of logic programs. This approach effectively positions the ATMS as a theorem prover for auto-epistemic logic, offering a procedural path for computing stable model semantics.
Introduction
In logic programming, the concept of "negation as failure"—the principle that a proposition is assumed false if it cannot be proven true—is a fundamental yet computationally challenging tool. To formalize this, researchers developed the Stable Model Semantics, which defines a stable model as a consistent "worldview" where every fact is justified by the program's rules and the assumptions made about what is false.
While theoretically robust, finding these stable models is a difficult task. Meanwhile, the artificial intelligence community had independently developed the Assumption-Based Truth Maintenance System (ATMS), a specialized tool for tracking conclusions derived from hypothetical assumptions. This research addresses whether the existing machinery of the ATMS can be leveraged to perform the heavy lifting required to identify stable models.
Methodology
The proposed framework utilizes a three-step pipeline to translate logic programs into a format manageable by an ATMS and subsequently extract stable models.
1. Program Transformation ($P \rightarrow P^*$)
The original logic program $P$, which may contain negations (e.g., $\sim q$), is converted into a Horn clause program $P^*$. In this transformation, every negative condition $\sim q$ is replaced by a new, explicit assumption $q^*$. To maintain logical consistency, the system is provided with "justifications" ensuring that $q$ and $q^*$ are treated as complements; they cannot both be true within the same model.
2. ATMS Processing
The transformed program $P^*$ and the set of new assumptions $S$ are processed by the ATMS. The system performs two primary functions:
- Identifying Nogoods: The ATMS detects sets of assumptions that lead to a logical contradiction.
- Labeling: The system determines the minimal sets of assumptions required to prove any given proposition within the program.
3. The Search for Stable Generators
The core of the algorithm involves identifying stable generators. A stable generator is a subset of assumptions that satisfies two conditions:
- Consistency: It does not contain any "nogood" sets.
- Completeness: For every assumption $n^*$ not included in the set, the corresponding proposition $n$ must be provable from the set.
The paper introduces a backtracking algorithm, implemented in Prolog as the procedure stcomp, which sifts through the ATMS outputs to find these generators. This procedure employs filtering techniques to prune the search space, ensuring that the selection of one assumption does not inadvertently invalidate the requirements of other program components.
Key Insights
Negation as Hypothesis
A central contribution of this work is the treatment of "negation as failure" as a hypothetical assumption rather than a standard logical operator. This shift allows the ATMS to manage negations using its existing dependency-tracking infrastructure.
Bridging Logic and Belief
The research highlights a deep connection between logic programming and auto-epistemic logic, which concerns how agents reason about their own beliefs. By demonstrating that an ATMS can compute stable models, the author suggests that ATMS structures are fundamentally linked to the representation of stable expansions of belief.
Results and Formal Correctness
The paper provides mathematical proofs (Theorems 1 and 2) establishing that every stable generator corresponds to exactly one stable model, and vice versa. This formalizes the correctness of the stcomp procedure. Furthermore, the work successfully demonstrates that stable model semantics can be viewed as a specific application of truth maintenance, providing a unified framework for researchers in both logic programming and automated reasoning.
Limitations and Future Directions
Despite its theoretical success, the current algorithm is limited to propositional logic. Extending the framework to first-order logic would require significant advancements in "grounding" techniques or the development of a more complex ATMS. Additionally, while the ATMS is efficient at dependency tracking, the search for stable generators remains non-deterministic and involves backtracking, leaving room for future complexity analysis and performance benchmarking.
Finally, the author notes that these findings are a subset of a broader link between stable models and abductive hypothesis generation, suggesting that future research could further unify these fields into a single theory of automated reasoning.
Summary updated